Fáry's theorem for 1-planar graphs

Seok Hee Hong, Peter Eades, Giuseppe Liotta, Sheung Hung Poon

Research output: Journal PublicationConference articlepeer-review

60 Citations (Scopus)

Abstract

A plane graph is a graph embedded in a plane without edge crossings. Fáry's theorem states that every plane graph can be drawn as a straight-line drawing, preserving the embedding of the plane graph. In this paper, we extend Fáry's theorem to a class of non-planar graphs. More specifically, we study the problem of drawing 1-plane graphs with straight-line edges. A 1-plane graph is a graph embedded in a plane with at most one crossing per edge. We give a characterisation of those 1-plane graphs that admit a straight-line drawing. The proof of the characterisation consists of a linear time testing algorithm and a drawing algorithm. Further, we show that there are 1-plane graphs for which every straight-line drawing has exponential area. To the best of our knowledge, this is the first result to extend Fáry's theorem to non-planar graphs.

Original languageEnglish
Pages (from-to)335-346
Number of pages12
JournalLecture Notes in Computer Science
Volume7434 LNCS
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event18th Annual International Computing and Combinatorics Conference, COCOON 2012 - Sydney, NSW, Australia
Duration: 20 Aug 201222 Aug 2012

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'Fáry's theorem for 1-planar graphs'. Together they form a unique fingerprint.

Cite this