Characterization of Unlabeled Level Planar Graphs

Fowler, J. Joseph and Kobourov, Stephen G. (2008) Characterization of Unlabeled Level Planar Graphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 37-49(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_7
Classifications: M Methods > M.500 Layered
P Styles > P.480 Layered

Actions (login required)

View Item View Item