Home | Issues | About JGAA | Instructions for Authors |
Selected Papers from the 1999 Symposium on Graph Drawing
DOI: 10.7155/jgaa.00046
Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
Vol. 6, no. 1, pp. 115-129, 2002. Regular paper.
Abstract The existing literature gives efficient algorithms for mapping trees or
less restrictively outerplanar graphs on a given set of points
in a plane, so that the edges are drawn planar and as straight lines.
We relax the latter requirement and allow very few bends on each edge
while considering general plane graphs.
Our results show two algorithms for mapping four-connected plane graphs
with at most one bend per edge and for mapping general plane graphs
with at most two bends per edge. Furthermore we give a point set,
where for arbitrary plane graphs it is NP-complete to decide whether
there is an mapping such that each edge has at most one bend.
|
Journal Supporters
|