Characterization of Unlabeled Radial Level Planar GraphsFowler, J. Joseph (2010) Characterization of Unlabeled Radial Level Planar Graphs. In: Graph Drawing 17th International Symposium, GD 2009, September 2225, 2009 , pp. 8193(Official URL: http://dx.doi.org/10.1007/9783642118050_10). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642118050_10
AbstractSuppose that an nvertex graph has a distinct labeling with the integers {1, . . . , n}. Such a graph is radial level planar if it admits a crossingsfree 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 lineartime drawing algorithms for any URLP graph.
Actions (login required)
