On Visibility Representation of Plane Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Huaming Zhang , Xin He

ABSTRACT

In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [11], Tamassia and Tollis [14] independently gave linear time VR algorithms for 2-connected plane graph. Recently, Lin et. al. reduced the width bound to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor \frac{22n - 42}{15} \rfloor$\end{document} [10]. In this paper, we prove that any plane graph G has a VR with width 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{13n - 24}{9} \rfloor$\end{document}.For a 4-connected plane triangulation G, we give a visibility representation of G with height at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lceil \frac{3n}{4} \rceil$\end{document}. In order to show that, we first show that every such graph has a canonical ordering tree with at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lceil \frac{n+1}{2} \rceil$\end{document} leaves instead of the previously known bound \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 + 1}{3} \rfloor$\end{document}, which is of independent interest. All of them can be obtained in linear time. More... »

PAGES

477-488

Book

TITLE

STACS 2004

ISBN

978-3-540-21236-2
978-3-540-24749-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_42

DOI

http://dx.doi.org/10.1007/978-3-540-24749-4_42

DIMENSIONS

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


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": "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, 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": "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Xin", 
        "id": "sg:person.011352641523.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [11], Tamassia and Tollis [14] independently gave linear time VR algorithms for 2-connected plane graph. Recently, Lin et. al. reduced the width bound to \\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{22n - 42}{15} \\rfloor$\\end{document} [10]. In this paper, we prove that any plane graph G has a VR with width 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}$\\lfloor \\frac{13n - 24}{9} \\rfloor$\\end{document}.For a 4-connected plane triangulation G, we give a visibility representation of G with height 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}$\\lceil \\frac{3n}{4} \\rceil$\\end{document}. In order to show that, we first show that every such graph has a canonical ordering tree with 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}$\\lceil \\frac{n+1}{2} \\rceil$\\end{document} leaves instead of the previously known bound \\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 + 1}{3} \\rfloor$\\end{document}, which is of independent interest. All of them can be obtained in linear time.", 
    "editor": [
      {
        "familyName": "Diekert", 
        "givenName": "Volker", 
        "type": "Person"
      }, 
      {
        "familyName": "Habib", 
        "givenName": "Michel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24749-4_42", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21236-2", 
        "978-3-540-24749-4"
      ], 
      "name": "STACS 2004", 
      "type": "Book"
    }, 
    "keywords": [
      "segments", 
      "time", 
      "ET", 
      "height", 
      "VR", 
      "interest", 
      "width", 
      "order", 
      "vertical line segments", 
      "Lin et", 
      "trees", 
      "leaves", 
      "representation", 
      "graph G", 
      "vertices", 
      "horizontal line segments", 
      "line segments", 
      "paper", 
      "adjacent vertices", 
      "algorithm", 
      "graph", 
      "Rosenstiehl", 
      "triangulation G", 
      "plane graph G", 
      "Tarjan", 
      "VR algorithm", 
      "plane graph", 
      "such graphs", 
      "independent interest", 
      "linear time", 
      "visibility representation", 
      "Tamassia", 
      "Tollis", 
      "linear time VR algorithms", 
      "time VR algorithms", 
      "plane triangulation G", 
      "canonical ordering tree", 
      "ordering tree"
    ], 
    "name": "On Visibility Representation of Plane Graphs", 
    "pagination": "477-488", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036759274"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24749-4_42"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24749-4_42", 
      "https://app.dimensions.ai/details/publication/pub.1036759274"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_153.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-24749-4_42"
  }
]
 

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-540-24749-4_42'

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-24749-4_42'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_42'

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-24749-4_42'


 

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

110 TRIPLES      23 PREDICATES      64 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24749-4_42 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nc493db4b81d64a8fab5767c6a18c536d
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [11], Tamassia and Tollis [14] independently gave linear time VR algorithms for 2-connected plane graph. Recently, Lin et. al. reduced the width bound to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor \frac{22n - 42}{15} \rfloor$\end{document} [10]. In this paper, we prove that any plane graph G has a VR with width 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{13n - 24}{9} \rfloor$\end{document}.For a 4-connected plane triangulation G, we give a visibility representation of G with height at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lceil \frac{3n}{4} \rceil$\end{document}. In order to show that, we first show that every such graph has a canonical ordering tree with at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lceil \frac{n+1}{2} \rceil$\end{document} leaves instead of the previously known bound \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 + 1}{3} \rfloor$\end{document}, which is of independent interest. All of them can be obtained in linear time.
7 schema:editor N1fb4f1b8f3494ee5b292950578982198
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N418b33ea5b054a95af64dd75fb64aaae
12 schema:keywords ET
13 Lin et
14 Rosenstiehl
15 Tamassia
16 Tarjan
17 Tollis
18 VR
19 VR algorithm
20 adjacent vertices
21 algorithm
22 canonical ordering tree
23 graph
24 graph G
25 height
26 horizontal line segments
27 independent interest
28 interest
29 leaves
30 line segments
31 linear time
32 linear time VR algorithms
33 order
34 ordering tree
35 paper
36 plane graph
37 plane graph G
38 plane triangulation G
39 representation
40 segments
41 such graphs
42 time
43 time VR algorithms
44 trees
45 triangulation G
46 vertical line segments
47 vertices
48 visibility representation
49 width
50 schema:name On Visibility Representation of Plane Graphs
51 schema:pagination 477-488
52 schema:productId N959387d208274105a03c3a03416d6ad2
53 Ndf4c3ec55d2d4182a83b058111843b9f
54 schema:publisher Nd57d8e2c8277494db987550ff61cb349
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036759274
56 https://doi.org/10.1007/978-3-540-24749-4_42
57 schema:sdDatePublished 2021-12-01T19:57
58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
59 schema:sdPublisher N4529d32df32b42909b9a7738d1f7bfca
60 schema:url https://doi.org/10.1007/978-3-540-24749-4_42
61 sgo:license sg:explorer/license/
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
64 N1fb4f1b8f3494ee5b292950578982198 rdf:first N3f3ae1731c2a49bf8bf1bf14c4396d5c
65 rdf:rest N2b3020ce3c79441390d13f2d0d6df1e2
66 N2b3020ce3c79441390d13f2d0d6df1e2 rdf:first N36cbed617ea140b8a50f84cd07b7fc86
67 rdf:rest rdf:nil
68 N36cbed617ea140b8a50f84cd07b7fc86 schema:familyName Habib
69 schema:givenName Michel
70 rdf:type schema:Person
71 N3f3ae1731c2a49bf8bf1bf14c4396d5c schema:familyName Diekert
72 schema:givenName Volker
73 rdf:type schema:Person
74 N418b33ea5b054a95af64dd75fb64aaae schema:isbn 978-3-540-21236-2
75 978-3-540-24749-4
76 schema:name STACS 2004
77 rdf:type schema:Book
78 N4529d32df32b42909b9a7738d1f7bfca schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N56befda15bce40caa0409b230995dc58 rdf:first sg:person.011352641523.42
81 rdf:rest rdf:nil
82 N959387d208274105a03c3a03416d6ad2 schema:name doi
83 schema:value 10.1007/978-3-540-24749-4_42
84 rdf:type schema:PropertyValue
85 Nc493db4b81d64a8fab5767c6a18c536d rdf:first sg:person.012041227127.88
86 rdf:rest N56befda15bce40caa0409b230995dc58
87 Nd57d8e2c8277494db987550ff61cb349 schema:name Springer Nature
88 rdf:type schema:Organisation
89 Ndf4c3ec55d2d4182a83b058111843b9f schema:name dimensions_id
90 schema:value pub.1036759274
91 rdf:type schema:PropertyValue
92 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
93 schema:name Mathematical Sciences
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
96 schema:name Pure Mathematics
97 rdf:type schema:DefinedTerm
98 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
99 schema:familyName He
100 schema:givenName Xin
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
102 rdf:type schema:Person
103 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.273335.3
104 schema:familyName Zhang
105 schema:givenName Huaming
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
107 rdf:type schema:Person
108 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
109 schema:name Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
110 rdf:type schema:Organization
 




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


...