Hanani-Tutte for Radial Planarity

Fulek, Radoslav and Pelsmajer, Michael J. and Schaefer, Marcus (2015) Hanani-Tutte for Radial Planarity. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 99-110 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_9).

Full text not available from this repository.

Abstract

A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1,…,Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.

Item Type:Conference Paper
Classifications:P Styles > P.480 Layered
P Styles > P.540 Planar
P Styles > P.660 Radial
Z Theory > Z.750 Topology
ID Code:1481

Repository Staff Only: item control page

References

Bachmaier, C., Brandenburg, F.J., Forster, M.: Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl. 9, 2005 (2005)

Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335–379 (1976)

Cairns, G., Nikolayevsky, Y.: Bounds for generalized thrackles. Discrete Comput. Geom. 23(2), 191–206 (2000)

Chimani, M., Zeranski, R.: Upward planarity testing: a computational study. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 13–24. Springer, Heidelberg (2013)

Chojnacki, C., Hanani, H.: Über wesentlich unplättbare Kurven im dreidimensionalen Raume. Fundamenta Mathematicae 23, 135–142 (1934)

Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Syst. Man Cybern. 18(6), 1035–1046 (1989)

Di Giacomo, E., Didimo, W., Liotta, G.: Spine and radial drawings, chapter 8. In: Roberto, T. (ed.) Handbook of Graph Drawing and Visualization. Discrete Mathematics and Its Applications. Chapman and Hall/CRC, Boca Raton (2013)

Fulek, R., Kynčl, J., Malinović, I., Pálvölgyi, D.: Clustered planarity testing revisited. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 428–439. Springer, Heidelberg (2014)

Fulek, R., Pelsmajer, M., Schaefer, M., Štefankovič, D.: Hanani-Tutte, monotone drawings, and level-planarity. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 263–287. Springer, New York (2013)

Gross, J.L., Tucker, T.W.: Topological Graph Theory. Dover Publications Inc., Mineola (2001). Reprint of the 1987 original

Gutwenger, C., Mutzel, P., Schaefer, M.: Practical experience with Hanani-Tutte for testing c-planarity. In: McGeoch, C.C., Meyer, U. (eds.) 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 86–97. SIAM, Portland (2014)

Jünger, M., Leipert, S.: Level planar embedding in linear time. J. Graph Algorithms Appl. 6(1), 72–81 (2002)

Northway, M.L.: A method for depicting social relationships obtained by sociometric testing. Sociometry 3(2), 144–150 (1940)

Pach, J., Tóth, G.: Monotone drawings of planar graphs. J. Graph Theory 46(1), 39–47 (2004). Updated version: arXiv:​1101.​0967

Pelsmajer, M.J., Schaefer, M., Stasi, D.: Strong Hanani-Tutte on the projective plane. SIAM J. Discrete Math. 23(3), 1317–1323 (2009)

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing even crossings. J. Combin. Theor. Ser. B 97(4), 489–500 (2007)

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing even crossings on surfaces. Eur. J. Comb. 30(7), 1704–1717 (2009)

Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. J. Graph Algortihms Appl. 17(4), 367–440 (2013)

Schaefer, M.: Hanani-Tutte and related results. In: Bárány, I., Böröczky, K.J., Tóth, G.F., Pach, J. (eds.) A Tribute to László Fejes Tóth. Bolyai Society Mathematical Studies, vol. 24, pp. 259–299. Springer, Berlin (2014)

Tutte, W.T.: Toward a theory of crossing numbers. J. Comb. Theor. 8, 45–53 (1970)

Wiedemann, D.H.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theor. 32(1), 54–62 (1986)