Triangulating planar graphs while minimizing the maximum degree

Goos Kant; Hans Bodlaender

doi:10.1007/3-540-55706-7_22

Triangulating planar graphs while minimizing the maximum degree

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

Abstract

In this paper we study the problem of triangulating a planar graph G while minimizing the maximum degree Δ(G′) of the resulting triangulated planar graph G′. It is shown that this problem is NP-complete. Worst-case lower bounds for Δ(G′) with respect to Δ(G) are given. We describe a linear algorithm to triangulate planar graphs, for which the maximum degree of the triangulated graph is only a constant larger than the lower bounds. Finally we show that triangulating one face while minimizing the maximum degree can be achieved in polynomial time. We use this algorithm to obtain a polynomial exact algorithm to triangulate the interior faces of an outerplanar graph while minimizing the maximum degree.

Original language	English
Title of host publication	Algorithm Theory — SWAT '92
Subtitle of host publication	Third Scandinavian Workshop on Algorithm Theory Helsinki, Finland, July 8–10, 1992 Proceedings
Editors	Otto Nurmi, Esko Ukkonen
Publisher	Springer
Pages	258-271
Number of pages	14
Volume	621
ISBN (Electronic)	978-3-540-47275-9
ISBN (Print)	978-3-540-55706-7
DOIs	https://doi.org/10.1007/3-540-55706-7_22
Publication status	Published - 1992

Publication series

Name	Lecture Notes in Computer Science

Access to Document

10.1007/3-540-55706-7_22

http://dx.doi.org/10.1007/3-540-55706-7_22

Cite this

Kant, G., & Bodlaender, H. (1992). Triangulating planar graphs while minimizing the maximum degree. In O. Nurmi, & E. Ukkonen (Eds.), Algorithm Theory — SWAT '92: Third Scandinavian Workshop on Algorithm Theory Helsinki, Finland, July 8–10, 1992 Proceedings (Vol. 621, pp. 258-271). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/3-540-55706-7_22

@inbook{a7c3084b9d9c4460a0b9c377d7eab275,

title = "Triangulating planar graphs while minimizing the maximum degree",

abstract = "In this paper we study the problem of triangulating a planar graph G while minimizing the maximum degree Δ(G′) of the resulting triangulated planar graph G′. It is shown that this problem is NP-complete. Worst-case lower bounds for Δ(G′) with respect to Δ(G) are given. We describe a linear algorithm to triangulate planar graphs, for which the maximum degree of the triangulated graph is only a constant larger than the lower bounds. Finally we show that triangulating one face while minimizing the maximum degree can be achieved in polynomial time. We use this algorithm to obtain a polynomial exact algorithm to triangulate the interior faces of an outerplanar graph while minimizing the maximum degree.",

author = "Goos Kant and Hans Bodlaender",

year = "1992",

doi = "10.1007/3-540-55706-7_22",

language = "English",

isbn = "978-3-540-55706-7",

volume = "621",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "258--271",

editor = "Otto Nurmi and Esko Ukkonen",

booktitle = "Algorithm Theory — SWAT '92",

}

Triangulating planar graphs while minimizing the maximum degree. / Kant, Goos; Bodlaender, Hans.
Algorithm Theory — SWAT '92: Third Scandinavian Workshop on Algorithm Theory Helsinki, Finland, July 8–10, 1992 Proceedings. ed. / Otto Nurmi; Esko Ukkonen. Vol. 621 Springer, 1992. p. 258-271 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Triangulating planar graphs while minimizing the maximum degree

AU - Kant, Goos

AU - Bodlaender, Hans

PY - 1992

Y1 - 1992

N2 - In this paper we study the problem of triangulating a planar graph G while minimizing the maximum degree Δ(G′) of the resulting triangulated planar graph G′. It is shown that this problem is NP-complete. Worst-case lower bounds for Δ(G′) with respect to Δ(G) are given. We describe a linear algorithm to triangulate planar graphs, for which the maximum degree of the triangulated graph is only a constant larger than the lower bounds. Finally we show that triangulating one face while minimizing the maximum degree can be achieved in polynomial time. We use this algorithm to obtain a polynomial exact algorithm to triangulate the interior faces of an outerplanar graph while minimizing the maximum degree.

AB - In this paper we study the problem of triangulating a planar graph G while minimizing the maximum degree Δ(G′) of the resulting triangulated planar graph G′. It is shown that this problem is NP-complete. Worst-case lower bounds for Δ(G′) with respect to Δ(G) are given. We describe a linear algorithm to triangulate planar graphs, for which the maximum degree of the triangulated graph is only a constant larger than the lower bounds. Finally we show that triangulating one face while minimizing the maximum degree can be achieved in polynomial time. We use this algorithm to obtain a polynomial exact algorithm to triangulate the interior faces of an outerplanar graph while minimizing the maximum degree.

U2 - 10.1007/3-540-55706-7_22

DO - 10.1007/3-540-55706-7_22

M3 - Chapter

SN - 978-3-540-55706-7

VL - 621

T3 - Lecture Notes in Computer Science

SP - 258

EP - 271

BT - Algorithm Theory — SWAT '92

A2 - Nurmi, Otto

A2 - Ukkonen, Esko

PB - Springer

ER -

Triangulating planar graphs while minimizing the maximum degree

Abstract

Publication series

Access to Document

Fingerprint

Cite this