# Planar Polyline Drawings via Graph Transformations

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2008-08-15

AUTHORS ABSTRACT

We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$W\leq\lfloor\frac{2n-2}{3}\rfloor$\end{document} , and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$W+H\leq\lfloor \frac{4n-4}{3}\rfloor$\end{document} . It uses at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor\frac{2n-5}{3}\rfloor$\end{document} bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2). More... »

PAGES

381-397

TITLE

Algorithmica

ISSUE

2

VOLUME

57

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-008-9215-x

DOI

http://dx.doi.org/10.1007/s00453-008-9215-x

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1032949578

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA",
"id": "http://www.grid.ac/institutes/grid.265893.3",
"name": [
"Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA"
],
"type": "Organization"
},
"familyName": "Zhang",
"givenName": "Huaming",
"id": "sg:person.012041227127.88",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-36379-3_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003004205",
"https://doi.org/10.1007/3-540-36379-3_4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/pl00009290",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1040398436",
"https://doi.org/10.1007/pl00009290"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf00353652",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015637021",
"https://doi.org/10.1007/bf00353652"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-36494-3_44",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009890571",
"https://doi.org/10.1007/3-540-36494-3_44"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11618058_17",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014203093",
"https://doi.org/10.1007/11618058_17"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-77537-9_22",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050806102",
"https://doi.org/10.1007/978-3-540-77537-9_22"
],
"type": "CreativeWork"
}
],
"datePublished": "2008-08-15",
"datePublishedReg": "2008-08-15",
"description": "We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder\u2019s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol.\u00a02607, pp.\u00a0499\u2013510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universit\u00e4t Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol.\u00a03843, pp.\u00a0177\u2013188, Springer, Berlin, 2005; He, SIAM J.\u00a0Comput. 22:1218\u20131226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W\u00d7H, where \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$W\\leq\\lfloor\\frac{2n-2}{3}\\rfloor$\\end{document}\n, and \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$W+H\\leq\\lfloor \\frac{4n-4}{3}\\rfloor$\\end{document}\n. It uses at most \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\lfloor\\frac{2n-5}{3}\\rfloor$\\end{document} \nbends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline drawing algorithm proposed in Bonichon et\u00a0al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol.\u00a02573, pp.\u00a035\u201346, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n\u22122).",
"genre": "article",
"id": "sg:pub.10.1007/s00453-008-9215-x",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"plane graph",
"irreducible triangulations",
"Planar Polyline Drawings",
"triangular interior faces",
"linear-time transformation",
"grid of size",
"linear time algorithm",
"plane triangulations",
"polyline drawings",
"Schnyder\u2019s realizers",
"separating triangles",
"time transformation",
"graph algorithms",
"transversal structure",
"graph",
"time algorithm",
"graph transformation",
"interior faces",
"algorithm",
"important relations",
"triangulation",
"such applications",
"polylines",
"exterior face",
"vertices",
"small number",
"realizers",
"transformation",
"grid",
"problem",
"bend",
"triangle",
"edge",
"applications",
"et",
"structure",
"number",
"al",
"relation",
"size",
"face",
"drawings",
"example",
"area"
],
"name": "Planar Polyline Drawings via Graph Transformations",
"pagination": "381-397",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1032949578"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-008-9215-x"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-008-9215-x",
"https://app.dimensions.ai/details/publication/pub.1032949578"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:24",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_452.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-008-9215-x"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-008-9215-x'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-008-9215-x'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-008-9215-x'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-008-9215-x'

This table displays all metadata directly associated to this object as RDF triples.

127 TRIPLES      22 PREDICATES      76 URIs      62 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N67901804874c4c50b1014cc9b26705f9
4 schema:citation sg:pub.10.1007/11618058_17
5 sg:pub.10.1007/3-540-36379-3_4
6 sg:pub.10.1007/3-540-36494-3_44
7 sg:pub.10.1007/978-3-540-77537-9_22
8 sg:pub.10.1007/bf00353652
9 sg:pub.10.1007/pl00009290
10 schema:datePublished 2008-08-15
11 schema:datePublishedReg 2008-08-15
12 schema:description We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$W\leq\lfloor\frac{2n-2}{3}\rfloor$\end{document} , and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$W+H\leq\lfloor \frac{4n-4}{3}\rfloor$\end{document} . It uses at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor\frac{2n-5}{3}\rfloor$\end{document} bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2).
13 schema:genre article
14 schema:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf N05d02c7c83b54dc792f682e5245d0da2
17 N84d95aa4125c40519e0b6eac80a2d81f
18 sg:journal.1047644
19 schema:keywords Planar Polyline Drawings
20 Schnyder’s realizers
21 al
22 algorithm
23 applications
24 area
25 bend
26 drawings
27 edge
28 et
29 example
30 exterior face
31 face
32 graph
33 graph algorithms
34 graph transformation
35 grid
36 grid of size
37 important relations
38 interior faces
39 irreducible triangulations
40 linear time algorithm
41 linear-time transformation
42 number
43 plane graph
44 plane triangulations
45 polyline drawings
46 polylines
47 problem
49 realizers
50 relation
51 separating triangles
52 size
53 small number
54 structure
55 such applications
56 time algorithm
57 time transformation
58 transformation
59 transversal structure
60 triangle
61 triangular interior faces
62 triangulation
63 vertices
64 schema:name Planar Polyline Drawings via Graph Transformations
65 schema:pagination 381-397
67 N8be2d38cf715488f833e46337568bc9c
68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032949578
69 https://doi.org/10.1007/s00453-008-9215-x
70 schema:sdDatePublished 2022-05-20T07:24
72 schema:sdPublisher N962a95492c194345b876895ee1b9bce2
73 schema:url https://doi.org/10.1007/s00453-008-9215-x
75 sgo:sdDataset articles
76 rdf:type schema:ScholarlyArticle
78 rdf:type schema:PublicationVolume
80 schema:value pub.1032949578
81 rdf:type schema:PropertyValue
82 N67901804874c4c50b1014cc9b26705f9 rdf:first sg:person.012041227127.88
83 rdf:rest rdf:nil
84 N84d95aa4125c40519e0b6eac80a2d81f schema:issueNumber 2
85 rdf:type schema:PublicationIssue
86 N8be2d38cf715488f833e46337568bc9c schema:name doi
87 schema:value 10.1007/s00453-008-9215-x
88 rdf:type schema:PropertyValue
89 N962a95492c194345b876895ee1b9bce2 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
95 schema:name Computation Theory and Mathematics
96 rdf:type schema:DefinedTerm
97 sg:journal.1047644 schema:issn 0178-4617
98 1432-0541
99 schema:name Algorithmica
100 schema:publisher Springer Nature
101 rdf:type schema:Periodical
102 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
103 schema:familyName Zhang
104 schema:givenName Huaming
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
106 rdf:type schema:Person
107 sg:pub.10.1007/11618058_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014203093
108 https://doi.org/10.1007/11618058_17
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/3-540-36379-3_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003004205
111 https://doi.org/10.1007/3-540-36379-3_4
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/3-540-36494-3_44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009890571
114 https://doi.org/10.1007/3-540-36494-3_44
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/978-3-540-77537-9_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050806102
117 https://doi.org/10.1007/978-3-540-77537-9_22
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/bf00353652 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015637021
120 https://doi.org/10.1007/bf00353652
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/pl00009290 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040398436
123 https://doi.org/10.1007/pl00009290
124 rdf:type schema:CreativeWork
125 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
126 schema:name Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
127 rdf:type schema:Organization