Simple Realizability of Complete Abstract Topological Graphs Simplified

Kynčl, Jan (2015) Simple Realizability of Complete Abstract Topological Graphs Simplified. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 309-320 (Official URL:

Full text not available from this repository.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.770 Planarity Testing
M Methods > M.100 Algebraic
Z Theory > Z.750 Topology
ID Code:1498

Repository Staff Only: item control page


Ábrego, B.M., Aichholzer, O., Fernández-Merchant, S., Hackl, T., Pammer, J., Pilz, A., Ramos, P., Salazar, G., Vogtenhuber, B.: All good drawings of small complete graphs, EuroCG 2015, Book of abstracts, pp. 57–60 (2015)

Aichholzer, O.: Personal communication. 2014

Armas-Sanabria, L., González-Acuña, F., Rodríguez-Viorato, J.: Self-intersection numbers of paths in compact surfaces. J. Knot Theor. Ramif. 20(3), 403–410 (2011)

Balko, M., Fulek, R., Kynčl, J.: Crossing numbers and combinatorial characterization of monotone drawings of KnKn. Discrete Comput. Geom. 53(1), 107–143 (2015)

Chimani, M.: Facets in the crossing number polytope. SIAM J. Discrete Math. 25(1), 95–111 (2011)

Farb, B., Thurston, B.: Homeomorphisms and simple closed curves, unpublished manuscript

Gioan, E.: Complete graph drawings up to triangle mutations. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 139–150. Springer, Heidelberg (2005)

Harborth, H., Mengersen, I.: Drawings of the complete graph with maximum number of crossings, In: Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing, (Boca Raton, FL, 1992), Congressus Numerantium, 88 pp. 225–228 (1992)

Hass, J., Scott, P.: Intersections of curves on surfaces. Isr. J. Math. 51(1–2), 90–120 (1985)

Kratochvíl, J., Lubiw, A., Nešetřil, J.: Noncrossing subgraphs in topological layouts. SIAM J. Discrete Math. 4(2), 223–244 (1991)

Kratochvíl, J., Matoušek, J.: NP-hardness results for intersection graphs. Commentationes Math. Univ. Carol. 30, 761–773 (1989)

Kynčl, J.: Enumeration of simple complete topological graphs. Eur. J. Comb. 30(7), 1676–1685 (2009)

Kynčl, J.: Simple realizability of complete abstract topological graphs in P. Discrete Comput. Geom. 45(3), 383–399 (2011)

Kynčl, J.: Improved enumeration of simple topological graphs. Discrete Comput. Geom. 50(3), 727–770 (2013)

Mutzel, P.: Recent advances in exact crossing minimization (extended abstract). Electron. Notes Discrete Math. 31, 33–36 (2008)

Pach, J., Tóth, G.: How many ways can one draw a graph? Combinatorica 26(5), 559–576 (2006)

Schaefer, M., Sedgwick, E., Štefankovič, D.: Computing Dehn twists and geometric intersection numbers in polynomial time, In: Proceedings of the 20th Canadian Conference on Computational Geometry, CCCG 2008, pp. 111–114 2008