×

An annotated bibliography on 1-planarity. (English) Zbl 1398.68402

Summary: The notion of 1-planarity is among the most natural and most studied generalizations of graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at most another edge. The study of 1-planar graphs dates back to more than fifty years ago and, recently, it has driven increasing attention in the areas of graph theory, graph algorithms, graph drawing, and computational geometry. This annotated bibliography aims to provide a guiding reference to researchers who want to have an overview of the large body of literature about 1-planar graphs. It reviews the current literature covering various research streams about 1-planarity, such as characterization and recognition, combinatorial properties, and geometric representations. As an additional contribution, we offer a list of open problems on 1-planar graphs.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
68-02 Research exposition (monographs, survey articles) pertaining to computer science

Software:

gCol
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baker, B. S., Approximation algorithms for NP-complete problems on planar graphs, J. ACM, 41, 1, 153-180 (1994) · Zbl 0807.68067
[2] Fox, J.; Pach, J.; Suk, A., The number of edges in \(k\)-quasi-planar graphs, SIAM J. Discrete Math., 27, 1, 550-561 (2013) · Zbl 1268.05051
[3] Pach, J.; Tóth, G., Graphs drawn with few crossings per edge, Combinatorica, 17, 3, 427-439 (1997) · Zbl 0902.05017
[4] Suk, A.; Walczak, B., New bounds on the maximum number of edges in \(k\)-quasi-planar graphs, Comput. Geom., 50, 24-33 (2015) · Zbl 1328.05056
[5] Huang, W.; Eades, P.; Hong, S.-H., Larger crossing angles make graphs easier to read, J. Vis. Lang. Comput., 25, 4, 452-465 (2014)
[6] Purchase, H. C., Which aesthetic has the greatest effect on human understanding?, (GD 1997. GD 1997, LNCS, vol. 1353 (1997), Springer), 248-261
[7] Purchase, H. C., Effective information visualisation: a study of graph drawing aesthetics and algorithms, Interact. Comput., 13, 2, 147-162 (2000)
[8] Purchase, H. C.; Carrington, D. A.; Allder, J., Empirical evaluation of aesthetics-based graph layout, Empir. Softw. Eng., 7, 3, 233-255 (2002) · Zbl 1010.68636
[9] Ringel, G., Ein Sechsfarbenproblem auf der kugel, Abh. Math. Sem. Univ. Hamburg, 29, 1-2, 107-117 (1965) · Zbl 0132.20701
[10] Borodin, O. V., Solution of the ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs, Metody Diskret. Analiz, 108, 12-26 (1984) · Zbl 0565.05027
[11] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G., Algorithms for drawing graphs: an annotated bibliography, Comput. Geom., 4, 235-282 (1994) · Zbl 0804.68001
[12] Bondy, J. A.; Murty, U. S.R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics (2007), Springer) · Zbl 1134.05001
[13] Diestel, R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 173 (2012), Springer)
[14] Gibbons, A., Algorithmic Graph Theory (1985), Cambridge University Press · Zbl 0568.05001
[15] (Harary, F., Graph Theory (1972), Addison-Wesley) · Zbl 0235.05105
[16] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G., Graph Drawing: Algorithms for the Visualization of Graphs (1999), Prentice-Hall · Zbl 1057.68653
[17] (Jünger, M.; Mutzel, P., Graph Drawing Software (2004), Springer) · Zbl 1107.90458
[18] (Kaufmann, M.; Wagner, D., Drawing Graphs. Methods and Models. Drawing Graphs. Methods and Models, LNCS, vol. 2025 (2001), Springer) · Zbl 0977.68644
[19] Nishizeki, T.; Rahman, M. S., (Planar Graph Drawing. Planar Graph Drawing, Lecture Notes Series on Computing, vol. 12 (2004), World Scientific) · Zbl 1070.68124
[20] Sugiyama, K., (Graph Drawing and Applications for Software and Knowledge Engineers. Graph Drawing and Applications for Software and Knowledge Engineers, Series on Software Engineering and Knowledge Engineering, vol. 11 (2002), World Scientific) · Zbl 1011.68068
[21] Tamassia, R., Advances in the theory and practice of graph drawing, Theoret. Comput. Sci., 217, 2, 235-254 (1999) · Zbl 0914.68207
[22] (Tamassia, R., Handbook on Graph Drawing and Visualization (2013), Chapman & Hall/CRC) · Zbl 1275.68033
[23] Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 1, 150-168 (1932) · JFM 58.0609.01
[24] Bodendiek, R.; Schumacher, H.; Wagner, K., Bemerkungen zu einem Sechsfarbenproblem von G. Ringel, Abh. Math. Sem. Univ. Hamburg, 53, 1, 41-52 (1983) · Zbl 0495.05020
[25] Albertson, M. O., Chromatic number, independence ratio, and crossing number, Ars Math. Contemp., 1, 1 (2008) · Zbl 1181.05032
[26] Zhang, X., Drawing complete multipartite graphs on the plane with restrictions on crossings, Acta Math. Sin. (Engl. Ser.), 30, 12, 2045-2053 (2014) · Zbl 1304.05031
[27] Czap, J.; Šugerek, P., Drawing graph joins in the plane with restrictions on crossings, Filomat, 31, 2, 363-370 (2017) · Zbl 1488.05133
[28] Chen, Z.; Kouno, M., A linear-time algorithm for 7-coloring 1-plane graphs, Algorithmica, 43, 3, 147-177 (2005) · Zbl 1082.05084
[29] Dujmović, V.; Eppstein, D.; Wood, D. R., Structure of graphs with locally restricted crossings, SIAM J. Discrete Math., 31, 2, 805-824 (2017) · Zbl 1362.05121
[30] Korzhik, V. P.; Mohar, B., Minimal obstructions for 1-immersions and hardness of 1-planarity testing, J. Graph Theory, 72, 1, 30-71 (2013) · Zbl 1259.05046
[31] Bodendiek, R.; Schumacher, H.; Wagner, K., Uber 1-optimale graphen, Math. Nachr., 117, 1, 323-339 (1984) · Zbl 0558.05017
[32] Suzuki, Y., Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math., 24, 4, 1527-1540 (2010) · Zbl 1221.05099
[33] Chepoi, V.; Dragan, F.; Vaxès, Y., Center and diameter problems in plane triangulations and quadrangulations, (ACM-SIAM SODA 2002 (2002), SIAM), 346-355 · Zbl 1058.05058
[34] Chang, G. J., Algorithmic Aspects of Domination in Graphs, 221-282 (2013), Springer: Springer New York, NY
[35] Brinkmann, G.; Greenberg, S.; Greenhill, C. S.; McKay, B. D.; Thomas, R.; Wollan, P., Generation of simple quadrangulations of the sphere, Discrete Math., 305, 1-3, 33-54 (2005) · Zbl 1078.05023
[36] Suzuki, Y., Optimal 1-planar graphs which triangulate other surfaces, Discrete Math., 310, 1, 6-11 (2010) · Zbl 1188.05056
[37] Chen, Z.; Grigni, M.; Papadimitriou, C. H., Planar map graphs, (STOC 1998 (1998), ACM), 514-523 · Zbl 1028.68104
[38] Chen, Z.; Grigni, M.; Papadimitriou, C. H., Map graphs, J. ACM, 49, 2, 127-138 (2002) · Zbl 1323.05039
[39] Chen, Z.; Grigni, M.; Papadimitriou, C. H., Recognizing hole-free 4-map graphs in cubic time, Algorithmica, 45, 2, 227-262 (2006) · Zbl 1095.68076
[40] Thorup, M., Map graphs in polynomial time, (FOCS 1998 (1998), IEEE), 396-405
[42] Czap, J.; Hudák, D., 1-planarity of complete multipartite graphs, Discrete Appl. Math., 160, 4-5, 505-512 (2012) · Zbl 1239.05039
[43] Grigoriev, A.; Bodlaender, H. L., Algorithms for graphs embeddable with few crossings per edge, Algorithmica, 49, 1, 1-11 (2007) · Zbl 1131.68120
[44] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039
[45] Bannister, M. J.; Cabello, S.; Eppstein, D., Parameterized complexity of 1-planarity, (WADS 2013. WADS 2013, LNCS, vol. 8037 (2013), Springer), 97-108 · Zbl 1390.68329
[46] Cabello, S.; Mohar, B., Adding one edge to planar graphs makes crossing number and 1-planarity hard, SIAM J. Comput., 42, 5, 1803-1829 (2013) · Zbl 1282.05033
[47] Brandenburg, F. J.; Didimo, W.; Evans, W. S.; Kindermann, P.; Liotta, G.; Montecchiani, F., Recognizing and drawing IC-planar graphs, Theoret. Comput. Sci., 636, 1-16 (2016) · Zbl 1342.68251
[49] Brandenburg, F. J., Recognizing optimal 1-planar graphs in linear time, Algorithmica (2016)
[50] Zhang, X.; Liu, G., The structure of plane graphs with independent crossings and its applications to coloring problems, Open Math., 11, 2, 308-321 (2013) · Zbl 1258.05028
[51] 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
[52] Hong, S.; Eades, P.; Katoh, N.; Liotta, G.; Schweitzer, P.; Suzuki, Y., A linear-time algorithm for testing outer-1-planarity, Algorithmica, 72, 4, 1033-1054 (2015) · Zbl 1319.68158
[54] Auer, C.; Brandenburg, F. J.; Gleißner, A.; Reislhuber, J., 1-planarity of graphs with a rotation system, J. Graph Algorithms Appl., 19, 1, 67-86 (2015) · Zbl 1307.05057
[55] Eades, P.; Hong, S.; Katoh, N.; Liotta, G.; Schweitzer, P.; Suzuki, Y., Testing maximal 1-planarity of graphs with a rotation system in linear time, (GD 2012. GD 2012, LNCS, vol. 7704 (2013), Springer), 339-345 · Zbl 1377.68172
[56] Downey, R. G.; Fellows, M. R., (Parameterized Complexity. Parameterized Complexity, Monographs in Computer Science (1999), Springer) · Zbl 0914.68076
[57] Flum, J.; Grohe, M., (Parameterized Complexity Theory. Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series (2006), Springer) · Zbl 1087.68034
[58] Chaitin, G. J., Register allocation & spilling via graph coloring, SIGPLAN Not., 17, 6, 98-101 (1982)
[59] Lewis, R., A Guide To Graph Colouring: Algorithms and Applications (2016), Springer · Zbl 1330.05002
[60] Marx, D., Graph colouring problems and their applications in scheduling, Period. Polytech. Ser. Electr. Eng., 48, 1, 11-16 (2004)
[61] Appel, K.; Haken, W., (Every Planar Map is Four Colorable. Every Planar Map is Four Colorable, Contemporary Mathematics, vol. 98 (1989), AMS) · Zbl 0331.05106
[62] Borodin, O. V., A new proof of the 6 color theorem, J. Graph Theory, 19, 4, 507-521 (1995) · Zbl 0826.05027
[63] Král’, D.; Stacho, L., Coloring plane graphs with independent crossings, J. Graph Theory, 64, 3, 184-205 (2010) · Zbl 1208.05019
[64] Borodin, O.; Kostochka, A.; Raspaud, A.; Sopena, E., Acyclic colouring of 1-planar graphs, Discrete Appl. Math., 114, 1-3, 29-41 (2001) · Zbl 0996.05053
[65] Wang, W.; Lih, K.-W., Coupled choosability of plane graphs, J. Graph Theory, 58, 1, 27-44 (2008) · Zbl 1155.05016
[66] Vizing, V. G., On an estimate of the chromatic class of a \(p\)-graph, Diskret. Analiz, 3, 25-30 (1964)
[67] Zhang, X.; Wu, J.-L., On edge colorings of 1-planar graphs, Inf. Process. Lett., 111, 3, 124-128 (2011) · Zbl 1259.05050
[68] Zhang, X.; Liu, G., On edge colorings of 1-planar graphs without adjacent triangles, Inf. Process. Lett., 112, 4, 138-142 (2012) · Zbl 1239.05078
[69] Zhang, X.; Liu, G., On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Combin., 104, 431-436 (2012) · Zbl 1274.05186
[70] Zhang, X.; Liu, G.; Wu, J.-L., Edge covering pseudo-outerplanar graphs with forests, Discrete Math., 312, 18, 2788-2799 (2012) · Zbl 1248.05053
[72] Zhang, X.; Wu, J.; Liu, G., List edge and list total coloring of 1-planar graphs, Front. Math. China, 7, 5, 1005-1018 (2012) · Zbl 1254.05050
[74] Zhang, X.; Hou, J.; Liu, G., On total colorings of 1-planar graphs, J. Comb. Optim., 30, 1, 160-173 (2015) · Zbl 1317.05066
[75] Czap, J., A note on total colorings of 1-planar graphs, Inf. Process. Lett., 113, 14-16, 516-517 (2013) · Zbl 1285.05054
[76] Chen, Z.-Z., New bounds on the edge number of a \(k\)-map graph, J. Graph Theory, 55, 4, 267-290 (2007) · Zbl 1124.05029
[77] Fabrici, I.; Madaras, T., The structure of 1-planar graphs, Discrete Math., 307, 7-8, 854-865 (2007) · Zbl 1111.05026
[78] Didimo, W., Density of straight-line 1-planar graph drawings, Inf. Process. Lett., 113, 7, 236-240 (2013) · Zbl 1259.05107
[79] Ackerman, E., A note on 1-planar graphs, Discrete Appl. Math., 175, 104-108 (2014) · Zbl 1298.05081
[80] Brandenburg, F.-J.; Eppstein, D.; Gleißner, A.; Goodrich, M. T.; Hanauer, K.; Reislhuber, J., On the density of maximal 1-planar graphs, (GD 2012. GD 2012, LNCS, vol. 7704 (2013), Springer), 327-338 · Zbl 1377.68165
[81] Karpov, D. V., An upper bound on the number of edges in an almost planar bipartite graph, J. Math. Sci., 196, 6, 737-746 (2014) · Zbl 1298.05087
[82] Czap, J.; Przybylo, J.; Skrabul’áková, E., On an extremal problem in the class of bipartite 1-planar graphs, Discuss. Math. Graph Theory, 36, 1, 141-151 (2016) · Zbl 1329.05081
[83] Ding, G.; Oporowski, B.; Sanders, D. P.; Vertigan, D., Surfaces, tree-width, clique-minors, and partitions, J. Combin. Theory Ser. B, 79, 2, 221-246 (2000) · Zbl 1029.05041
[84] Elmallah, E. S.; Colbourn, C. J., Partitioning the edges of a planar graph into two partial \(k\)-trees, (CGTC 1988. CGTC 1988, Congressus Numerantium (1988), Utilitas Mathematica), 69-80 · Zbl 0677.05017
[85] Gonçalves, D., Edge partition of planar graphs into two outerplanar graphs, (STOC 2005 (2005), ACM), 504-512 · Zbl 1192.05113
[86] Kedlaya, K. S., Outerplanar partitions of planar graphs, J. Combin. Theory Ser. B, 67, 2, 238-248 (1996) · Zbl 0858.05040
[87] Czap, J.; Hudák, D., On drawings and decompositions of 1-planar graphs, Electron. J. Combin., 20, 2, P54 (2013) · Zbl 1295.05084
[88] Lenhart, W. J.; Liotta, G.; Montecchiani, F., On partitioning the edges of 1-plane graphs, Theoret. Comput. Sci., 662, 59-65 (2017) · Zbl 1357.05125
[89] Di Giacomo, E.; Didimo, W.; Evans, W. S.; Liotta, G.; Meijer, H.; Montecchiani, F.; Wismath, S. K., Ortho-polygon visibility representations of embedded graphs, Algorithmica (2017) · Zbl 1390.68497
[91] Angelini, P.; Di Battista, G.; Frati, F.; Patrignani, M.; Rutter, I., Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph, J. Discrete Algorithms, 14, 150-172 (2012) · Zbl 1247.05156
[92] Baur, M.; Brandes, U., Crossing reduction in circular layouts, (WG 2004. WG 2004, LNCS, vol. 3353 (2005), Springer), 332-343 · Zbl 1112.68408
[93] Chung, F. R.K.; Leighton, F. T.; Rosenberg, A. L., Embedding graphs in books: A layout problem with applications to VLSI design, SIAM J. Algebr. Discrete. Methods, 8, 1, 33-58 (1987) · Zbl 0617.68062
[94] Kainen, P. C., The book thickness of a graph. II, (CGTC 1990. CGTC 1990, Congressus Numerantium, number v. 5 (1990), Utilitas Mathematica), 127-132 · Zbl 0749.05030
[95] McKenzie, T.; Overbay, S., Book embeddings and zero divisors, Ars Combin., 95 (2010) · Zbl 1249.13018
[96] Wattenberg, M., Arc diagrams: visualizing structure in strings, (IEEE INFOVIS 2002 (2002), IEEE), 110-116
[97] Wood, D. R., Bounded degree book embeddings and three-dimensional orthogonal graph drawing, (GD 2001. GD 2001, LNCS, vol. 2265 (2002), Springer), 312-327 · Zbl 1054.68607
[98] Yannakakis, M., Embedding planar graphs in four pages, J. Comput. System Sci., 38, 1, 36-67 (1989) · Zbl 0673.05022
[99] Malitz, S., Graphs with \(E\) edges have pagenumber \(O(\sqrt{E})\), J. Algorithms, 17, 1, 71-84 (1994) · Zbl 0810.68102
[100] Bekos, M. A.; Bruckdorfer, T.; Kaufmann, M.; Raftopoulou, C. N., 1-planar graphs have constant book thickness, (ESA 2015. ESA 2015, LNCS, vol. 9294 (2015), Springer), 130-141 · Zbl 1370.05046
[102] Bekos, M. A.; Kaufmann, M.; Zielke, C., The book embedding problem from a SAT-solving perspective, (GD 2015. GD 2015, LNCS, vol. 9411 (2015), Springer), 125-138 · Zbl 1471.68184
[103] Dujmović, V.; Morin, P.; Wood, D., Layered separators in minor-closed families with applications, J. Combin. Theory Ser. B (2017) · Zbl 1371.05282
[104] Nešetřil, J.; de Mendez, P. O., (Sparsity - Graphs, Structures, and Algorithms. Sparsity - Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28 (2012), Springer) · Zbl 1268.05002
[105] Har-Peled, S.; Quanrud, K., Approximation algorithms for polynomial-expansion and low-density graphs, (ESA 2015. ESA 2015, LNCS, vol. 9294 (2015), Springer), 717-728 · Zbl 1466.68059
[106] Nešetřil, J.; de Mendez, P. O.; Wood, D. R., Characterisations and examples of graph classes with bounded expansion, European J. Combin., 33, 3, 350-373 (2012) · Zbl 1230.05250
[107] Hudák, D.; Šugerek, P., Light edges in 1-planar graphs with prescribed minimum degree, Discuss. Math. Graph Theory, 32, 3, 545-556 (2012) · Zbl 1262.05032
[108] Hudák, D.; Madaras, T., On local structure of 1-planar graphs of minimum degree 5 and girth 4, Discuss. Math. Graph Theory, 29, 2, 385-400 (2009) · Zbl 1194.05025
[109] Hudák, D.; Madaras, T.; Suzuki, Y., On properties of maximal 1-planar graphs, Discuss. Math. Graph Theory, 32, 4, 737-747 (2012) · Zbl 1293.05065
[110] Czap, J.; Hudák, D.; Madaras, T., Joins of 1-planar graphs, Acta Math. Sin. (Engl. Ser.), 30, 11, 1867-1876 (2014) · Zbl 1304.05024
[111] Bucko, J.; Czap, J., 1-planar lexicographic products of graphs, Appl. Math. Sci., 9, 109, 5441-5449 (2015)
[112] Thomassen, C., Rectilinear drawings of graphs, J. Graph Theory, 12, 3, 335-341 (1988) · Zbl 0649.05051
[113] Hong, S.; Eades, P.; Liotta, G.; Poon, S.-H., Fáry’s theorem for 1-planar graphs, (COCOON 2012. COCOON 2012, LNCS, vol. 7434 (2012), Springer), 335-346 · Zbl 1364.68308
[114] Hong, S.; Nagamochi, H., Re-embedding a 1-plane graph into a straight-line drawing in linear time, (GD 2016. GD 2016, LNCS, vol. 9801 (2016), Springer), 321-334 · Zbl 1478.68244
[115] Alam, M. J.; Brandenburg, F. J.; Kobourov, S. G., Straight-line grid drawings of 3-connected 1-planar graphs, (GD 2013. GD 2013, LNCS, vol. 8242 (2013), Springer), 83-94 · Zbl 1406.68054
[116] Di Giacomo, E.; Liotta, G.; Montecchiani, F., Drawing outer 1-planar graphs with few slopes, J. Graph Algorithms Appl., 19, 2, 707-741 (2015) · Zbl 1328.05131
[117] Erten, C.; Kobourov, S. G., Simultaneous embedding of a planar graph and its dual on the grid, Theory Comput. Syst., 38, 3, 313-327 (2005) · Zbl 1101.68726
[118] Dujmović, V.; Wood, D. R., Three-dimensional grid drawings with sub-quadratic volume, (Towards a Theory of Geometric Graphs. Towards a Theory of Geometric Graphs, Contemporary Mathematics, vol. 342 (2014), AMS), 55-66 · Zbl 1077.05066
[119] Huang, W., Using eye tracking to investigate graph layout effects, (APVIS 2007 (2007), IEEE), 97-100
[120] Huang, W.; Hong, S.; Eades, P., Effects of crossing angles, (PacificVis 2008 (2008), IEEE), 41-46
[121] Didimo, W.; Eades, P.; Liotta, G., Drawing graphs with right angle crossings, Theoret. Comput. Sci., 412, 39, 5156-5166 (2011) · Zbl 1225.68134
[122] Eades, P.; Liotta, G., Right angle crossing graphs and 1-planarity, Discrete Appl. Math., 161, 7-8, 961-969 (2013) · Zbl 1408.05042
[123] Bekos, M. A.; Didimo, W.; Liotta, G.; Mehrabi, S.; Montecchiani, F., On RAC drawings of 1-planar graphs, Theoret. Comput. Sci. (2017) · Zbl 1372.68202
[124] Dehkordi, H. R.; Eades, P., Every outer-1-plane graph has a right angle crossing drawing, Internat. J. Comput. Geom. Appl., 22, 6, 543-558 (2012) · Zbl 1267.68165
[125] Brightwell, G. R.; Scheinerman, E. R., Representations of planar graphs, SIAM J. Discrete Math., 6, 2, 214-229 (1993) · Zbl 0782.05026
[126] Mohar, B., Circle packings of maps in polynomial time, European J. Combin., 18, 7, 785-805 (1997) · Zbl 0891.52008
[127] Liotta, G.; Montecchiani, F., L-visibility drawings of IC-planar graphs, Inf. Process. Lett., 116, 3, 217-222 (2016) · Zbl 1328.68263
[128] Duchet, P.; Hamidoune, Y. O.; Vergnas, M. L.; Meyniel, H., Representing a planar graph by vertical lines joining different levels, Discrete Math., 46, 3, 319-321 (1983) · Zbl 0516.05023
[129] Otten, R. H.J. M.; Wijk, J. G.V., Graph representations in interactive layout design, (IEEE ISCSS (1978), IEEE), 914-918
[130] Rosenstiehl, P.; Tarjan, R. E., Rectilinear planar layouts and bipolar orientations of planar graphs, Discr. & Comput. Geom., 1, 343-353 (1986) · Zbl 0607.05027
[131] Tamassia, R.; Tollis, I. G., A unified approach to visibility representations of planar graphs, Discr. & Comput. Geom., 1, 1, 321-341 (1986) · Zbl 0607.05026
[132] Thomassen, C., Plane representations of graphs, (Progress in Graph Theory (1984), AP), 43-69 · Zbl 0554.05021
[133] Wismath, S. K., Characterizing bar line-of-sight graphs, (SoCG 1985 (1985), ACM), 147-152
[134] Dean, A. M.; Evans, W. S.; Gethner, E.; Laison, J. D.; Safari, M. A.; Trotter, W. T., Bar \(k\)-visibility graphs, J. Graph Algorithms Appl., 11, 1, 45-59 (2007) · Zbl 1161.68651
[135] Brandenburg, F. J., 1-visibility representations of 1-planar graphs, J. Graph Algorithms Appl., 18, 3, 421-438 (2014) · Zbl 1301.05238
[136] Evans, W. S.; Kaufmann, M.; Lenhart, W.; Mchedlidze, T.; Wismath, S. K., Bar 1-visibility graphs vs. other nearly planar graphs, J. Graph Algorithms Appl., 18, 5, 721-739 (2014) · Zbl 1305.05160
[137] Evans, W. S.; Liotta, G.; Montecchiani, F., Simultaneous visibility representations of plane st-graphs using L-shapes, Theoret. Comput. Sci., 645, 100-111 (2016) · Zbl 1348.68174
[138] Biedl, T. C.; Liotta, G.; Montecchiani, F., On visibility representations of non-planar graphs, (SoCG 2016. SoCG 2016, LIPIcs, vol. 51 (2016)), 19:1-19:16, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik · Zbl 1387.68241
[139] Shermer, T. C., On rectangle visibility graphs. III. External visibility and complexity, (CCCG 1996 (1996), Carleton University Press), 234-239
[140] Alam, M. J.; Evans, W. S.; Kobourov, S. G.; Pupyrev, S.; Toeniskoetter, J.; Ueckerdt, T., Contact representations of graphs in 3D, (WADS 2015. WADS 2015, LNCS, vol. 9214 (2015), Springer), 14-27 · Zbl 1444.68130
[141] Liotta, G., Graph drawing beyond planarity: some results and open problems, (ICTCS 2014. ICTCS 2014, CEUR Workshop Proceedings, vol. 1231 (2014), CEUR-WS.org.), 3-8
[142] Hakimi, S.; Mitchem, J.; Schmeichel, E., Star arboricity of graphs, Discrete Math., 149, 1, 93-98 (1996) · Zbl 0843.05037
[143] Nishizeki, T.; Baybars, I., Lower bounds on the cardinality of the maximum matchings of planar graphs, Discrete Math., 28, 3, 255-267 (1979) · Zbl 0425.05032
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.