FHSV05.pdf (130.8 kB)
Outerplanar crossing numbers of 3-row meshes, Halin graphs and complete p-partite graphs
online resourceposted on 2006-09-25, 13:40 authored by R. Fulek, Hongmei He, Ondrej Sykora, Imrich Vrt'o
An outerplanar (also called circular, convex, one-page) drawing of an n-vertex graph G is a drawing in which the vertices are placed on a circle and each edge is drawn using one straight-line segment. We derive exact results for the minimal number of crossings in any outerplanar drawings of the following classes of graphs: 3-row meshes, Halin graphs and complete p−partite graphs with equal size partite sets.
- Computer Science
CitationFULEK et al, 2005. Outerplanar crossing numbers of 3-row meshes, Halin graphs and complete p-partite graphs. IN: Vojtáš et al (eds.), Proceedings of the 31st Annual Conference on Current Trends in Theory and Practice of Computer Science, Liptovský Ján, Slovakia, January 22-28, 2005. Lecture notes in computer science, 3381, Berlin : Springer Verlag, pp. 376-379
Publisher© Springer Verlag
NotesThis is a conference paper. The definitive version is available from: http://springerlink.metapress.com/content/105633/?sortorder=asc&p_o=719