×

zbMATH — the first resource for mathematics

Recognizing optimal 1-planar graphs in linear time. (English) Zbl 1386.68116
Summary: A graph with \(n\) vertices is 1-planar if it can be drawn in the plane such that each edge is crossed at most once, and is optimal if it has the maximum of \(4n-8\) edges. We show that optimal 1-planar graphs can be recognized in linear time. Our algorithm implements a graph reduction system with two rules, which can be used to reduce every optimal 1-planar graph to an irreducible extended wheel graph. The graph reduction system is non-deterministic, constraint, and non-confluent.

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
Software:
LEDA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Argyriou, EN; Bekos, MA; Symvonis, A, The straight-line RAC drawing problem is NP-hard, J. Graph Algorithms Appl., 16, 569-597, (2012) · Zbl 1254.05120
[2] Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Outer 1-planar graphs. Algorithmica 74(4), 1293-1320 (2016) · Zbl 1339.68197
[3] Auer, C; Brandenburg, FJ; Gleißner, A; Reislhuber, J, 1-planarity of graphs with a rotation system, J. Graph Algorithms Appl., 19, 67-86, (2015) · Zbl 1307.05057
[4] Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. In: Dehne, F., Solis-Oba, R., Sack, J. (eds.) WADS 2013. LNCS, vol. 8037, pp. 97-108 (2013) · Zbl 1390.68329
[5] Bekos, M.A., Cornelsen, S., Grilli, L., Hong, S., Kaufmann, M.: On the recognition of fan-planar and maximal outer-fan-planar graphs. In: Duncan, C.A., Symvonis, A. (eds.) GD 2014. pp. 198-209 (2014) · Zbl 1426.68200
[6] Binucci, C; Giacomo, E; Didimo, W; Montecchiani, F; Patrignani, M; Symvonis, A; Tollis, IG, Fan-planarity: properties and complexity, Theor. Comput. Sci., 589, 76-86, (2015) · Zbl 1317.68134
[7] Bodendiek, R; Schumacher, H; Wagner, K, Bemerkungen zu einem sechsfarbenproblem von G. ringel, Abh. aus dem Math. Seminar der Univ. Hamburg, 53, 41-52, (1983) · Zbl 0495.05020
[8] Bodendiek, R; Schumacher, H; Wagner, K, Über 1-optimale graphen, Mathematische Nachrichten, 117, 323-339, (1984) · Zbl 0558.05017
[9] Brandenburg, F.J.: On 4-map graphs and 1-planar graphs and their recognition problem. CoRR (2015), arXiv:1509.03447 · Zbl 0902.05017
[10] Brandenburg, F.J.: A reduction system for optimal 1-planar graphs. CoRR (2016). arXiv:1602.06407 · Zbl 1228.05175
[11] Brandenburg, F.J.: The computational complexity of certain graph grammars. In: Cremers, A.B., Kriegel, H. (eds.) 6th GI-Conference Theoretical Computer Science. LNCS, vol. 145, pp. 91-99. Springer (1983) · Zbl 1323.05039
[12] Brandenburg, FJ; Didimo, W; Evans, WS; Kindermann, P; Liotta, G; Montecchianti, F, Recognizing and drawing IC-planar graphs, Theor. Comput. Sci., 636, 1-16, (2016) · Zbl 1342.68251
[13] Brandenburg, F.J., Eppstein, D., Gleißner, A., Goodrich, M.T., Hanauer, K., Reislhuber, J.: On the density of maximal 1-planar graphs. In: van Kreveld, M., Speckmann, B. (eds.) GD 2012. LNCS, vol. 7704, pp. 327-338. Springer (2013) · Zbl 1377.68165
[14] Brinkmann, G; Greenberg, S; Greenhill, C; McKay, BD; Thomas, R; Wollan, P, Generation of simple quadrangulations of the sphere, Discrete Math., 305, 33-54, (2005) · Zbl 1078.05023
[15] Cabello, S; Mohar, B, Adding one edge to planar graphs makes crossing number and 1-planarity hard, SIAM J. Comput., 42, 1803-1829, (2013) · Zbl 1282.05033
[16] Chen, Z; Grigni, M; Papadimitriou, CH, Map graphs, J. ACM, 49, 127-138, (2002) · Zbl 1323.05039
[17] Chen, Z; Grigni, M; Papadimitriou, CH, Recognizing hole-free 4-map graphs in cubic time, Algorithmica, 45, 227-262, (2006) · Zbl 1095.68076
[18] Corradini, A; Montanari, U; Rossi, F; Ehrig, H; Heckel, R; Löwe, M; Rozenberg, G (ed.), Algebraic approaches to graph transformations, 163-245, (1997), Singapore
[19] Battista, G; Tamassia, R, On-line planarity testing, SIAM J. Comput., 25, 956-997, (1996) · Zbl 0858.68063
[20] Didimo, W, Density of straight-line 1-planar graph drawings, Inform. Process. Lett., 113, 236-240, (2013) · Zbl 1259.05107
[21] Eades, P; Hong, SH; Katoh, N; Liotta, G; Schweitzer, P; Suzuki, Y, A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system, Theor. Comput. Sci., 513, 65-76, (2013) · Zbl 1407.68354
[22] Eades, P; Liotta, G, Right angle crossing graphs and 1-planarity, Discret. Appl. Math., 161, 961-969, (2013) · Zbl 1408.05042
[23] Eggleton, RB, Rectilinear drawings of graphs, Utilitas Math., 29, 149-172, (1986) · Zbl 0578.05016
[24] Grigoriev, A; Bodlaender, HL, Algorithms for graphs embeddable with few crossings per edge, Algorithmica, 49, 1-11, (2007) · Zbl 1131.68120
[25] Gutwenger, C; Mutzel, P; Marks, J (ed.), A linear time implementation of SPQR-trees, No. 1984, 77-90, (2001), Berlin · Zbl 1043.68621
[26] Hong, S; Eades, P; Katoh, N; Liotta, G; Schweitzer, P; Suzuki, Y, A linear-time algorithm for testing outer-1-planarity, Algorithmica, 72, 1033-1054, (2015) · Zbl 1319.68158
[27] Hong, SH; Eades, P; Liotta, G; Poon, SH; Gudmundsson, J (ed.); Mestre, J (ed.); Viglas, T (ed.), Fáry’s theorem for 1-planar graphs, No. 7434, 335-346, (2012), Berlin · Zbl 1364.68308
[28] Korzhik, VP; Mohar, B, Minimal obstructions for 1-immersion and hardness of 1-planarity testing, J. Graph Theor., 72, 30-71, (2013) · Zbl 1259.05046
[29] Kyncl, J, Enumeration of simple complete topological graphs, Eur. J. Comb., 30, 1676-1685, (2009) · Zbl 1228.05175
[30] Mehlhorn, K., Näher, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999) · Zbl 0976.68156
[31] Pach, J; Tóth, G, Graphs drawn with a few crossings per edge, Combinatorica, 17, 427-439, (1997) · Zbl 0902.05017
[32] Patrignani, M; Tamassia, R (ed.), Planarity testing and embedding, (2013), Boca Raton
[33] Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. aus dem Math. Seminar der Univ. Hamburg 29, 107-117 (1965) · Zbl 0132.20701
[34] Rozenberg, G.: Handbook of Graph Grammars and Computing by Graph Transformation. World Scientific, Singapore (1997) · Zbl 0908.68095
[35] Schumacher, H, Zur struktur 1-planarer graphen, Mathematische Nachrichten, 125, 291-300, (1986) · Zbl 0594.05026
[36] Suzuki, Y, Re-embeddings of maximum 1-planar graphs, SIAM J. Discret. Math., 24, 1527-1540, (2010) · Zbl 1221.05099
[37] Whitney, H, Planar graphs, Fund. Math., 21, 73-84, (1933) · JFM 59.1235.03
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.