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, Chicago, IL, USA , pp. 81-93 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_10).

Full text not available from this repository.

Abstract

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
ID Code:1086

Repository Staff Only: item control page

References

Bachmaier, C., Brandenburg, F.J., Forster, M.: Radial level planarity testing and embedding in linear time. Journal of Graph Algorithms and Applications 9(1), 53–97 (2005)

Brandes, U., Kenis, P., Wagner, D.: Communicating centrality in policy network drawings. IEEE Transactions on Visualization and Computer Graphics 09(2), 241– 253 (2003)

Brass, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous graph embedding. Computational Geometry: Theory and Applications 36(2), 117–130 (2007)

Cappos, J., Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Simultaneous graph embedding with bends and circular arcs. Computational Geometry: Theory and Applications 42(2), 173–182 (2009)

Eades, P., Feng, Q., Lin, X., Nagamochi, H.: Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica 44(1), 1–32 (2006)

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 367–379. Springer, Heidelberg (2007)

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. Computational Geometry: Theory and Applications 42(7), 704–721 (2009)

Fowler, J.J.: Characterization of unlabeled radial level planar graphs. Technical Report TR09-03, University of Arizona (2009), http://ulp.cs.arizona.edu/TR09-03.pdf

Fowler, J.J.: Unlabeled Level Planarity. PhD thesis, University of Arizona (2009), http://ulp.cs.arizona.edu/ulp-thesis.pdf

Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled planar graphs. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 37–49. Springer, Heidelberg (2008)

Jünger, M., Leipert, S.: Level planar embedding in linear time. Journal of Graph Algorithms and Applications 6(1), 67–113 (2002)