Drawing Planar Graphs with Circular Arcs

C. C. Cheng, C. A. Duncan, M. T. Goodrich, S. G. Kobourov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular arc. We also give an algorithm for drawing n-vertex planar graphs such that the edges are sequences of two continuous circular arcs. The algorithm runs in O(n) time and embeds the graph on the O(n) × O(n) grid, while maintaining Θ(1=d(v)) angular resolution, where d(v) is the degree of vertex v. Since in this case we use circular arcs of infinite radius, this is also the first algorithm to simultaneously achieve good angular resolution, small area and at most one bend per edge using straight-line segments. Finally, we show how to create drawings in which edges are smooth C1-continuous curves, represented by a sequence of at most three circular arcs.

Original languageEnglish (US)
Title of host publicationGraph Drawing - 7th International Symposium, GD 1999, Proceedings
EditorsJan Kratochvil
Number of pages10
ISBN (Print)3540669043, 9783540669043
StatePublished - 1999
Event7th International Symposium on Graph Drawing, GD 1999 - Prague, Czech Republic
Duration: Sep 15 1999Sep 19 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other7th International Symposium on Graph Drawing, GD 1999
Country/TerritoryCzech Republic

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Drawing Planar Graphs with Circular Arcs'. Together they form a unique fingerprint.

Cite this