Congestion in planar graphs with demands on faces
classification
💻 cs.DM
keywords
congestionfaceplanarachievealgorithmbetterboundarycannot
read the original abstract
We give an algorithm to route a multicommodity flow in a planar graph $G$ with congestion $O(\log k)$, where $k$ is the maximum number of terminals on the boundary of a face, when each demand edge lie on a face of $G$. We also show that our specific method cannot achieve a substantially better congestion.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.