Closed Rectangle-of-Influence Drawings for Irreducible Triangulations View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Sadish Sadasivam , Huaming Zhang

ABSTRACT

A closed rectangle-of-influence (RI for short) drawing is a straight-line grid drawing in which there is no other vertex inside or on the boundary of the axis parallel rectangle defined by the two end vertices of any edge. Biedl et al. [2] showed that a plane graph G has a closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior). They also showed that such a graph G has a closed RI drawing in an (n − 1) ×(n − 1) grid, where n is the number of vertices in G. They raised an open question on whether this grid size bound can be improved [2]. Without loss of generality, we investigate maximal plane graphs admitting closed RI drawings in this paper. They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations [7]. In this paper, we present a linear time algorithm that computes closed RI drawings for irreducible triangulations. Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a closed RI drawing with size at most (n − 3) ×(n − 3); and for a random irreducible triangulation, the expected grid size of the drawing is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$({22n \over 27}+O(\sqrt{n})) \times ({22n \over 27}+O(\sqrt{n}))$\end{document}. We then prove that for arbitrary n ≥ 4, there is an n-vertex irreducible triangulation, such that any of its closed RI drawing requires a grid of size (n − 3) ×(n − 3). Thus the grid size of the drawing produced by our algorithm is tight. This lower bound also answers the open question posed in [2] negatively. More... »

PAGES

409-418

Book

TITLE

Theory and Applications of Models of Computation

ISBN

978-3-642-13561-3
978-3-642-13562-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-13562-0_37

DOI

http://dx.doi.org/10.1007/978-3-642-13562-0_37

DIMENSIONS

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


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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "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": "Sadasivam", 
        "givenName": "Sadish", 
        "id": "sg:person.015341066775.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341066775.96"
        ], 
        "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"
        }, 
        "familyName": "Zhang", 
        "givenName": "Huaming", 
        "id": "sg:person.012041227127.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "A closed rectangle-of-influence (RI for short) drawing is a straight-line grid drawing in which there is no other vertex inside or on the boundary of the axis parallel rectangle defined by the two end vertices of any edge. Biedl et al. [2] showed that a plane graph G has a closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior). They also showed that such a graph G has a closed RI drawing in an (n\u2009\u2212\u20091) \u00d7(n\u2009\u2212\u20091) grid, where n is the number of vertices in G. They raised an open question on whether this grid size bound can be improved [2]. Without loss of generality, we investigate maximal plane graphs admitting closed RI drawings in this paper. They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations [7]. In this paper, we present a linear time algorithm that computes closed RI drawings for irreducible triangulations. Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a closed RI drawing with size at most (n\u2009\u2212\u20093) \u00d7(n\u2009\u2212\u20093); and for a random irreducible triangulation, the expected grid size of the drawing is \\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}$({22n \\over 27}+O(\\sqrt{n})) \\times ({22n \\over 27}+O(\\sqrt{n}))$\\end{document}. We then prove that for arbitrary n\u2009\u2265\u20094, there is an n-vertex irreducible triangulation, such that any of its closed RI drawing requires a grid of size (n\u2009\u2212\u20093) \u00d7(n\u2009\u2212\u20093). Thus the grid size of the drawing produced by our algorithm is tight. This lower bound also answers the open question posed in [2] negatively.", 
    "editor": [
      {
        "familyName": "Kratochv\u00edl", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Li", 
        "givenName": "Angsheng", 
        "type": "Person"
      }, 
      {
        "familyName": "Fiala", 
        "givenName": "Ji\u0159\u00ed", 
        "type": "Person"
      }, 
      {
        "familyName": "Kolman", 
        "givenName": "Petr", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-13562-0_37", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-13561-3", 
        "978-3-642-13562-0"
      ], 
      "name": "Theory and Applications of Models of Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "irreducible triangulations", 
      "grid size", 
      "closed rectangle", 
      "quadrangular exterior face", 
      "triangular interior faces", 
      "straight-line grid drawings", 
      "influence drawing", 
      "graph G", 
      "maximal plane graphs", 
      "plane graph", 
      "grid of size", 
      "number of vertices", 
      "plane graph G", 
      "linear time algorithm", 
      "grid drawing", 
      "axis-parallel rectangles", 
      "loss of generality", 
      "end vertices", 
      "time algorithm", 
      "vertices", 
      "open question", 
      "parallel rectangles", 
      "interior faces", 
      "graph", 
      "algorithm", 
      "triangulation G", 
      "rectangle", 
      "grid", 
      "triangulation", 
      "exterior face", 
      "generality", 
      "compute", 
      "edge", 
      "boundaries", 
      "size", 
      "number", 
      "drawings", 
      "questions", 
      "RI", 
      "face", 
      "loss", 
      "paper"
    ], 
    "name": "Closed Rectangle-of-Influence Drawings for Irreducible Triangulations", 
    "pagination": "409-418", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025151638"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-13562-0_37"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-13562-0_37", 
      "https://app.dimensions.ai/details/publication/pub.1025151638"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:43", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_188.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-13562-0_37"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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-642-13562-0_37'

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-642-13562-0_37'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13562-0_37'

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-642-13562-0_37'


 

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

124 TRIPLES      23 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-13562-0_37 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nda6e6b2cbfa443b8adf9a71236ae895b
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description A closed rectangle-of-influence (RI for short) drawing is a straight-line grid drawing in which there is no other vertex inside or on the boundary of the axis parallel rectangle defined by the two end vertices of any edge. Biedl et al. [2] showed that a plane graph G has a closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior). They also showed that such a graph G has a closed RI drawing in an (n − 1) ×(n − 1) grid, where n is the number of vertices in G. They raised an open question on whether this grid size bound can be improved [2]. Without loss of generality, we investigate maximal plane graphs admitting closed RI drawings in this paper. They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations [7]. In this paper, we present a linear time algorithm that computes closed RI drawings for irreducible triangulations. Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a closed RI drawing with size at most (n − 3) ×(n − 3); and for a random irreducible triangulation, the expected grid size of the drawing is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$({22n \over 27}+O(\sqrt{n})) \times ({22n \over 27}+O(\sqrt{n}))$\end{document}. We then prove that for arbitrary n ≥ 4, there is an n-vertex irreducible triangulation, such that any of its closed RI drawing requires a grid of size (n − 3) ×(n − 3). Thus the grid size of the drawing produced by our algorithm is tight. This lower bound also answers the open question posed in [2] negatively.
7 schema:editor N2ef96d11ecc94485b9b1c60254ca5c9f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb2416a6d0e314e848cb8567e4ebcbac4
12 schema:keywords RI
13 algorithm
14 axis-parallel rectangles
15 boundaries
16 closed rectangle
17 compute
18 drawings
19 edge
20 end vertices
21 exterior face
22 face
23 generality
24 graph
25 graph G
26 grid
27 grid drawing
28 grid of size
29 grid size
30 influence drawing
31 interior faces
32 irreducible triangulations
33 linear time algorithm
34 loss
35 loss of generality
36 maximal plane graphs
37 number
38 number of vertices
39 open question
40 paper
41 parallel rectangles
42 plane graph
43 plane graph G
44 quadrangular exterior face
45 questions
46 rectangle
47 size
48 straight-line grid drawings
49 time algorithm
50 triangular interior faces
51 triangulation
52 triangulation G
53 vertices
54 schema:name Closed Rectangle-of-Influence Drawings for Irreducible Triangulations
55 schema:pagination 409-418
56 schema:productId N3c05c30b12914449bf09e6e9e398d5a3
57 Ndbd105d724b443a3a05f8fbb4b3ab6e1
58 schema:publisher N17c3ccdb64fe43bc9e7e24847dde184c
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025151638
60 https://doi.org/10.1007/978-3-642-13562-0_37
61 schema:sdDatePublished 2022-05-20T07:43
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher Nbe38bdd943324ac3bf65d7e1d5c9f35c
64 schema:url https://doi.org/10.1007/978-3-642-13562-0_37
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N014f1b27e3d44266b0e4ee2b51840f07 schema:familyName Li
69 schema:givenName Angsheng
70 rdf:type schema:Person
71 N12ea9f3827c5480eb7ba77c20dd5edb4 schema:familyName Kratochvíl
72 schema:givenName Jan
73 rdf:type schema:Person
74 N17c3ccdb64fe43bc9e7e24847dde184c schema:name Springer Nature
75 rdf:type schema:Organisation
76 N2ef96d11ecc94485b9b1c60254ca5c9f rdf:first N12ea9f3827c5480eb7ba77c20dd5edb4
77 rdf:rest N8a35a482a6f1435c927593d14f03d575
78 N3c05c30b12914449bf09e6e9e398d5a3 schema:name dimensions_id
79 schema:value pub.1025151638
80 rdf:type schema:PropertyValue
81 N4443e80f787e449fac026a595339b32b rdf:first Na7e29bc59d2c4dbe84420c43e9e55ff6
82 rdf:rest rdf:nil
83 N58a0181d5e8b4ec48f5ca1ec177c9627 schema:familyName Fiala
84 schema:givenName Jiří
85 rdf:type schema:Person
86 N8a35a482a6f1435c927593d14f03d575 rdf:first N014f1b27e3d44266b0e4ee2b51840f07
87 rdf:rest Ndcf15ce7526848ce818670a88cf84af1
88 N9ae338bb38a647aeb6b0d7ebeba24c54 rdf:first sg:person.012041227127.88
89 rdf:rest rdf:nil
90 Na7e29bc59d2c4dbe84420c43e9e55ff6 schema:familyName Kolman
91 schema:givenName Petr
92 rdf:type schema:Person
93 Nb2416a6d0e314e848cb8567e4ebcbac4 schema:isbn 978-3-642-13561-3
94 978-3-642-13562-0
95 schema:name Theory and Applications of Models of Computation
96 rdf:type schema:Book
97 Nbe38bdd943324ac3bf65d7e1d5c9f35c schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 Nda6e6b2cbfa443b8adf9a71236ae895b rdf:first sg:person.015341066775.96
100 rdf:rest N9ae338bb38a647aeb6b0d7ebeba24c54
101 Ndbd105d724b443a3a05f8fbb4b3ab6e1 schema:name doi
102 schema:value 10.1007/978-3-642-13562-0_37
103 rdf:type schema:PropertyValue
104 Ndcf15ce7526848ce818670a88cf84af1 rdf:first N58a0181d5e8b4ec48f5ca1ec177c9627
105 rdf:rest N4443e80f787e449fac026a595339b32b
106 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
107 schema:name Mathematical Sciences
108 rdf:type schema:DefinedTerm
109 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
110 schema:name Pure Mathematics
111 rdf:type schema:DefinedTerm
112 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
113 schema:familyName Zhang
114 schema:givenName Huaming
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
116 rdf:type schema:Person
117 sg:person.015341066775.96 schema:affiliation grid-institutes:grid.265893.3
118 schema:familyName Sadasivam
119 schema:givenName Sadish
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341066775.96
121 rdf:type schema:Person
122 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
123 schema:name Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
124 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...