Algorithms for multi-level graph planarity testing and layout

Patrick Healy; Ago Kuusik

doi:10.1016/j.tcs.2004.02.033

Algorithms for multi-level graph planarity testing and layout

Patrick Healy
, Ago Kuusik

University of Limerick

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we consider the problems of testing a multi-level graph for planarity and laying out or, drawing, a multi-level graph in a clear way. We introduce a new abstraction of a common integer linear programming formulation of the problems that we call a vertex-exchange graph. We demonstrate how this concept can be used to solve the problems by providing clear and simple algorithms for testing a multi-level graph for planarity and laying out a multi-level graph when planar.

Original language	English
Pages (from-to)	331-344
Number of pages	14
Journal	Theoretical Computer Science
Volume	320
Issue number	2-3
DOIs	https://doi.org/10.1016/j.tcs.2004.02.033
Publication status	Published - 14 Jun 2004

Keywords

Level graph layout
Level graphs
Level planarity testing

Access to Document

10.1016/j.tcs.2004.02.033

Cite this

@article{d44886259791451089602abeb83d2fd4,

title = "Algorithms for multi-level graph planarity testing and layout",

abstract = "In this paper we consider the problems of testing a multi-level graph for planarity and laying out or, drawing, a multi-level graph in a clear way. We introduce a new abstraction of a common integer linear programming formulation of the problems that we call a vertex-exchange graph. We demonstrate how this concept can be used to solve the problems by providing clear and simple algorithms for testing a multi-level graph for planarity and laying out a multi-level graph when planar.",

keywords = "Level graph layout, Level graphs, Level planarity testing",

author = "Patrick Healy and Ago Kuusik",

year = "2004",

month = jun,

day = "14",

doi = "10.1016/j.tcs.2004.02.033",

language = "English",

volume = "320",

pages = "331--344",

journal = "Theoretical Computer Science",

issn = "0304-3975",

number = "2-3",

}

TY - JOUR

T1 - Algorithms for multi-level graph planarity testing and layout

AU - Healy, Patrick

AU - Kuusik, Ago

PY - 2004/6/14

Y1 - 2004/6/14

N2 - In this paper we consider the problems of testing a multi-level graph for planarity and laying out or, drawing, a multi-level graph in a clear way. We introduce a new abstraction of a common integer linear programming formulation of the problems that we call a vertex-exchange graph. We demonstrate how this concept can be used to solve the problems by providing clear and simple algorithms for testing a multi-level graph for planarity and laying out a multi-level graph when planar.

AB - In this paper we consider the problems of testing a multi-level graph for planarity and laying out or, drawing, a multi-level graph in a clear way. We introduce a new abstraction of a common integer linear programming formulation of the problems that we call a vertex-exchange graph. We demonstrate how this concept can be used to solve the problems by providing clear and simple algorithms for testing a multi-level graph for planarity and laying out a multi-level graph when planar.

KW - Level graph layout

KW - Level graphs

KW - Level planarity testing

UR - https://www.scopus.com/pages/publications/2442687127

U2 - 10.1016/j.tcs.2004.02.033

DO - 10.1016/j.tcs.2004.02.033

M3 - Article

AN - SCOPUS:2442687127

SN - 0304-3975

VL - 320

SP - 331

EP - 344

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2-3

ER -

Algorithms for multi-level graph planarity testing and layout

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this