A characterization of level planar graphs

Patrick Healy; Ago Kuusik; Sebastian Leipert

doi:10.1016/j.disc.2003.02.001

A characterization of level planar graphs

Patrick Healy, Ago Kuusik, Sebastian Leipert

Department of Computer Science & Information Systems

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

Abstract

We present a characterization of level planar graphs in terms of minimal forbidden subgraphs called minimal level non-planar (MLNP) subgraph patterns. We show that an MLNP subgraph pattern is completely characterized by either a tree, a level non-planar cycle or a level planar cycle with certain path augmentations.

Original language	English
Pages (from-to)	51-63
Number of pages	13
Journal	Discrete Mathematics
Volume	280
Issue number	1-3
DOIs	https://doi.org/10.1016/j.disc.2003.02.001
Publication status	Published - 6 Apr 2004

Keywords

Level graphs
Maximum level planar subgraph
Minimal non-planarity

Access to Document

10.1016/j.disc.2003.02.001

Cite this

@article{9da8aebde14a498cb35011122eb4b369,

title = "A characterization of level planar graphs",

abstract = "We present a characterization of level planar graphs in terms of minimal forbidden subgraphs called minimal level non-planar (MLNP) subgraph patterns. We show that an MLNP subgraph pattern is completely characterized by either a tree, a level non-planar cycle or a level planar cycle with certain path augmentations.",

keywords = "Level graphs, Maximum level planar subgraph, Minimal non-planarity",

author = "Patrick Healy and Ago Kuusik and Sebastian Leipert",

year = "2004",

month = apr,

day = "6",

doi = "10.1016/j.disc.2003.02.001",

language = "English",

volume = "280",

pages = "51--63",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "1-3",

}

TY - JOUR

T1 - A characterization of level planar graphs

AU - Healy, Patrick

AU - Kuusik, Ago

AU - Leipert, Sebastian

PY - 2004/4/6

Y1 - 2004/4/6

N2 - We present a characterization of level planar graphs in terms of minimal forbidden subgraphs called minimal level non-planar (MLNP) subgraph patterns. We show that an MLNP subgraph pattern is completely characterized by either a tree, a level non-planar cycle or a level planar cycle with certain path augmentations.

AB - We present a characterization of level planar graphs in terms of minimal forbidden subgraphs called minimal level non-planar (MLNP) subgraph patterns. We show that an MLNP subgraph pattern is completely characterized by either a tree, a level non-planar cycle or a level planar cycle with certain path augmentations.

KW - Level graphs

KW - Maximum level planar subgraph

KW - Minimal non-planarity

UR - http://www.scopus.com/inward/record.url?scp=1642292942&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2003.02.001

DO - 10.1016/j.disc.2003.02.001

M3 - Article

AN - SCOPUS:1642292942

SN - 0012-365X

VL - 280

SP - 51

EP - 63

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

A characterization of level planar graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this