pith. sign in

arxiv: 1008.3653 · v1 · pith:LXH5B4C5new · submitted 2010-08-21 · 💻 cs.DM

Congestion in planar graphs with demands on faces

classification 💻 cs.DM
keywords congestionfaceplanarachievealgorithmbetterboundarycannot
0
0 comments X
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.