# On Planar Polyline Drawings

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2008-01-01

AUTHORS ABSTRACT

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 (p + 1) ×(n − 2), where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$p \leq (\lfloor \frac{2n-5}{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}$p \leq \lfloor\frac{2n-5}{3}\rfloor$\end{document} bends, and each edge uses at most one bend. Compared with the area optimal polyline drawing algorithm in [3], our algorithm uses a larger grid size bound in trade for a smaller bound on the total number of bends. Their bend bound is (n − 2). Our algorithm is based on a transformation from Schnyder’s realizers [6,7] of maximal plane graphs to transversal structures [4,5] for maximal internally 4-connected plane graphs. This transformation reveals important relations between the two combinatorial structures for plane graphs, which is of independent interest. More... »

PAGES

213-218

### Book

TITLE

Graph Drawing

ISBN

978-3-540-77536-2
978-3-540-77537-9

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-77537-9_22

DOI

http://dx.doi.org/10.1007/978-3-540-77537-9_22

DIMENSIONS

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

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/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure 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"
},
{
"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"
},
"id": "sg:person.015341066775.96",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341066775.96"
],
"type": "Person"
}
],
"datePublished": "2008-01-01",
"datePublishedReg": "2008-01-01",
"description": "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 (p\u2009+\u20091) \u00d7(n\u2009\u2212\u20092), where \\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}$p \\leq (\\lfloor \\frac{2n-5}{3}\\rfloor)$\\end{document}. It uses at most \\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}$p \\leq \\lfloor\\frac{2n-5}{3}\\rfloor$\\end{document} bends, and each edge uses at most one bend. Compared with the area optimal polyline drawing algorithm in [3], our algorithm uses a larger grid size bound in trade for a smaller bound on the total number of bends. Their bend bound is (n\u2009\u2212\u20092). Our algorithm is based on a transformation from Schnyder\u2019s realizers [6,7] of maximal plane graphs to transversal structures [4,5] for maximal internally 4-connected plane graphs. This transformation reveals important relations between the two combinatorial structures for plane graphs, which is of independent interest.",
"editor": [
{
"familyName": "Hong",
"givenName": "Seok-Hee",
"type": "Person"
},
{
"familyName": "Nishizeki",
"givenName": "Takao",
"type": "Person"
},
{
"familyName": "Quan",
"givenName": "Wu",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-77537-9_22",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-77536-2",
"978-3-540-77537-9"
],
"name": "Graph Drawing",
"type": "Book"
},
"keywords": [
"plane graph",
"Planar Polyline Drawings",
"maximal plane graphs",
"grid of size",
"linear time algorithm",
"large grid sizes",
"combinatorial structure",
"polyline drawings",
"Schnyder\u2019s realizers",
"independent interest",
"grid size",
"transversal structure",
"time algorithm",
"graph",
"algorithm",
"important relations",
"polylines",
"vertices",
"realizers",
"grid",
"transformation",
"bend",
"structure",
"edge",
"size",
"total number",
"number",
"interest",
"relation",
"drawings",
],
"name": "On Planar Polyline Drawings",
"pagination": "213-218",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1050806102"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-77537-9_22"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-77537-9_22",
"https://app.dimensions.ai/details/publication/pub.1050806102"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:47",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_421.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-77537-9_22"
}
]

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/978-3-540-77537-9_22'

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/978-3-540-77537-9_22'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-77537-9_22'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-77537-9_22'

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

108 TRIPLES      23 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0101
3 schema:author Nbeddb87febcb4fa7bb72047a49bc7b83
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description 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 (p + 1) ×(n − 2), where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$p \leq (\lfloor \frac{2n-5}{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}$p \leq \lfloor\frac{2n-5}{3}\rfloor$\end{document} bends, and each edge uses at most one bend. Compared with the area optimal polyline drawing algorithm in [3], our algorithm uses a larger grid size bound in trade for a smaller bound on the total number of bends. Their bend bound is (n − 2). Our algorithm is based on a transformation from Schnyder’s realizers [6,7] of maximal plane graphs to transversal structures [4,5] for maximal internally 4-connected plane graphs. This transformation reveals important relations between the two combinatorial structures for plane graphs, which is of independent interest.
7 schema:editor N0d537f08c8df4790b401d6e618d8fe2d
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nccefd403d50d4af78b9bc04f71779759
12 schema:keywords Planar Polyline Drawings
13 Schnyder’s realizers
14 algorithm
15 bend
16 combinatorial structure
17 drawings
18 edge
19 graph
20 grid
21 grid of size
22 grid size
23 important relations
24 independent interest
25 interest
26 large grid sizes
27 linear time algorithm
28 maximal plane graphs
29 number
30 plane graph
31 polyline drawings
32 polylines
33 realizers
34 relation
35 size
36 structure
37 time algorithm
38 total number
40 transformation
41 transversal structure
42 vertices
43 schema:name On Planar Polyline Drawings
44 schema:pagination 213-218
45 schema:productId N664899cf473d4ae0b53cecc2b9e972ee
46 N9460e75e7b8440bbb896c93ec893acd2
47 schema:publisher N7b2e16981682468fa1c2da029c02d62a
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050806102
49 https://doi.org/10.1007/978-3-540-77537-9_22
50 schema:sdDatePublished 2022-05-20T07:47
52 schema:sdPublisher N627c9cec3d064d87b3f53203286349fc
53 schema:url https://doi.org/10.1007/978-3-540-77537-9_22
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N0d537f08c8df4790b401d6e618d8fe2d rdf:first N930f147eabb24a67a245b5c58ac01884
59 N627c9cec3d064d87b3f53203286349fc schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 N664899cf473d4ae0b53cecc2b9e972ee schema:name dimensions_id
62 schema:value pub.1050806102
63 rdf:type schema:PropertyValue
64 N7b2e16981682468fa1c2da029c02d62a schema:name Springer Nature
65 rdf:type schema:Organisation
66 N8f63f66c921a44f9b47b8899f2e38831 schema:familyName Nishizeki
67 schema:givenName Takao
68 rdf:type schema:Person
69 N930f147eabb24a67a245b5c58ac01884 schema:familyName Hong
70 schema:givenName Seok-Hee
71 rdf:type schema:Person
72 N9460e75e7b8440bbb896c93ec893acd2 schema:name doi
73 schema:value 10.1007/978-3-540-77537-9_22
74 rdf:type schema:PropertyValue
75 N98ef3826c07848b99d4b4bf0daee4698 schema:familyName Quan
76 schema:givenName Wu
77 rdf:type schema:Person
78 N9ce58b5d372e415c92bbb50cfc1180c2 rdf:first sg:person.015341066775.96
79 rdf:rest rdf:nil
80 Nbeddb87febcb4fa7bb72047a49bc7b83 rdf:first sg:person.012041227127.88
81 rdf:rest N9ce58b5d372e415c92bbb50cfc1180c2
83 rdf:rest Nf78a235ce9bb49c89bb6c6bc3b842588
84 Nccefd403d50d4af78b9bc04f71779759 schema:isbn 978-3-540-77536-2
85 978-3-540-77537-9
86 schema:name Graph Drawing
87 rdf:type schema:Book
88 Nf78a235ce9bb49c89bb6c6bc3b842588 rdf:first N98ef3826c07848b99d4b4bf0daee4698
89 rdf:rest rdf:nil
90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
91 schema:name Mathematical Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
94 schema:name Pure Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
97 schema:familyName Zhang
98 schema:givenName Huaming
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
100 rdf:type schema:Person
101 sg:person.015341066775.96 schema:affiliation grid-institutes:grid.265893.3