TY - GEN
T1 - Characterization of unlabeled level planar graphs
AU - Fowler, J. Joseph
AU - Kobourov, Stephen G.
PY - 2008
Y1 - 2008
N2 - We present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotone path on the same set of n vertices, for any of the n! possible mappings. These graphs are equivalent to the set of unlabeled level planar (ULP) graphs that are level planar over all possible labelings. Our contributions are twofold. First, we provide linear time drawing algorithms for ULP graphs. Second, we provide a complete characterization of ULP graphs by showing that any other graph must contain a subgraph homeomorphic to one of seven forbidden graphs.
AB - We present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotone path on the same set of n vertices, for any of the n! possible mappings. These graphs are equivalent to the set of unlabeled level planar (ULP) graphs that are level planar over all possible labelings. Our contributions are twofold. First, we provide linear time drawing algorithms for ULP graphs. Second, we provide a complete characterization of ULP graphs by showing that any other graph must contain a subgraph homeomorphic to one of seven forbidden graphs.
UR - http://www.scopus.com/inward/record.url?scp=49949102782&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=49949102782&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-77537-9_7
DO - 10.1007/978-3-540-77537-9_7
M3 - Conference contribution
AN - SCOPUS:49949102782
SN - 3540775366
SN - 9783540775362
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 37
EP - 49
BT - Graph Drawing - 15th International Symposium, GD 2007, Revised Papers
T2 - 15th International Symposium on Graph Drawing, GD 2007
Y2 - 24 September 2007 through 26 September 2007
ER -