On rectilinear drawing of graphs

Peter Eades, Seok Hee Hong, Sheung Hung Poon

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

8 Citations (Scopus)

Abstract

A rectilinear drawing is an orthogonal grid drawing without bends, possibly with edge crossings, without any overlapping between edges, between vertices, or between edges and vertices. Rectilinear drawings without edge crossings (planar rectilinear drawings) have been extensively investigated in graph drawing. Testing rectilinear planarity of a graph is NP-complete [10]. Restricted cases of the planar rectilinear drawing problem, sometimes called the "no-bend orthogonal drawing problem", have been well studied (see, for example,[13],[14],[15] ). In this paper, we study the problem of general non-planar rectilinear drawing; this problem has not received as much attention as the planar case. We consider a number of restricted classes of graphs and obtain a polynomial time algorithm, NP-hardness results, an FPT algorithm, and some bounds. We define a structure called a "4-cycle block". We give a linear time algorithm to test whether a graph that consists of a single 4-cycle block has a rectilinear drawing, and draw it if such a drawing exists. We show that the problem is NP-hard for the graphs that consist of 4-cycle blocks connected by single edges, as well as the case where each vertex has degree 2 or 4. We present a linear time fixed-parameter tractable algorithm to test whether a degree-4 graph has a rectilinear drawing, where the parameter is the number of degree-3 and degree-4 vertices of the graph. We also present a lower bound on the area of rectilinear drawings, and a upper bound on the number of edges.

Original languageEnglish
Title of host publicationGraph Drawing - 17th International Symposium, GD 2009, Revised Papers
Pages232-243
Number of pages12
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event17th International Symposium on Graph Drawing, GD 2009 - Chicago, IL, United States
Duration: 22 Sep 200925 Sep 2009

Publication series

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

Conference

Conference17th International Symposium on Graph Drawing, GD 2009
Country/TerritoryUnited States
CityChicago, IL
Period22/09/0925/09/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'On rectilinear drawing of graphs'. Together they form a unique fingerprint.

Cite this