Characterization of Unlabeled Radial Level Planar Graphs

Fowler, J. Joseph (2010) Characterization of Unlabeled Radial Level Planar Graphs. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009 , pp. 81-93(Official URL:

Full text not available from this repository.


Suppose that an n-vertex graph has a distinct labeling with the integers {1, . . . , n}. Such a graph is radial level planar if it admits a crossings-free drawing under two constraints. First, each vertex lies on a concentric circle such that the radius of the circle equals the label of the vertex. Second, each edge is drawn with a radially monotone curve. We characterize the set of unlabeled radial level planar (URLP) graphs that are radial level planar in terms of 7 and 15 forbidden subdivisions depending on whether the graph is disconnected or connected, respectively. We also provide linear-time drawing algorithms for any URLP graph.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-11805-0_10
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.660 Radial

Actions (login required)

View Item View Item