A Simple Quasi-planar Drawing of K10

Brandenburg, Franz J. (2016) A Simple Quasi-planar Drawing of K10. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 603-604.

Full text not available from this repository.

Abstract

We show that the complete graph on ten vertices K10 is a simple quasi-planar graph, which answers a question of Ackerman and Tardos [E. Ackerman and G. Tardos, On the maximum number of edges in quasi-planar graphs, J. Comb. Theory, Series A 114 (2007) 563–571]and shows that the bound 6.5n−20 on the maximum number of edges of simple quasi-planar graphs is tight for n=10.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1573

Actions (login required)

View Item View Item