On Representation of Planar Graphs by Segments View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008-01-01

AUTHORS

Sadish Sadasivam , Huaming Zhang

ABSTRACT

In this paper, we introduce Vertex-face contact representation (VFCR for short) for 2-connected plane multigraphs. We present a simple linear time algorithm for constructing a VFCR for 2-connected plane graphs. Our algorithm only uses an st-orientation for G and its corresponding st-orientation for the dual graph of G. We also show that one kind of vertex-vertex contact representation (VVCR) for 2-connected bipartite planar graphs introduced by Fraysseix et al. [2,3] can be easily obtained by applying our algorithm. In general, our algorithm produces a more compact representation than their algorithm.Then we investigate st-orientations for 3-connected planar graphs. We prove that a 3-connected planar graph G with n vertices and f faces, has an st-orientation with the length of its longest directed path \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\leq \frac{2n}{3}+2\lceil\sqrt{n/3}\rceil+5$\end{document}. This implies that such a graph G admits a VFCR in a grid with non-trivial size bound. This non-trivial size bound also applies to the vertex-vertex contact representation [2,3] for a large class of 2-connected bipartite planar graphs. More... »

PAGES

304-315

Book

TITLE

Algorithmic Aspects in Information and Management

ISBN

978-3-540-68865-5
978-3-540-68880-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-68880-8_29

DOI

http://dx.doi.org/10.1007/978-3-540-68880-8_29

DIMENSIONS

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


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": "2008-01-01", 
    "datePublishedReg": "2008-01-01", 
    "description": "In this paper, we introduce Vertex-face contact representation (VFCR for short) for 2-connected plane multigraphs. We present a simple linear time algorithm for constructing a VFCR for 2-connected plane graphs. Our algorithm only uses an st-orientation for G and its corresponding st-orientation for the dual graph of G. We also show that one kind of vertex-vertex contact representation (VVCR) for 2-connected bipartite planar graphs introduced by Fraysseix et al. [2,3] can be easily obtained by applying our algorithm. In general, our algorithm produces a more compact representation than their algorithm.Then we investigate st-orientations for 3-connected planar graphs. We prove that a 3-connected planar graph G with n vertices and f faces, has an st-orientation with the length of its longest directed path \\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}$\\leq \\frac{2n}{3}+2\\lceil\\sqrt{n/3}\\rceil+5$\\end{document}. This implies that such a graph G admits a VFCR in a grid with non-trivial size bound. This non-trivial size bound also applies to the vertex-vertex contact representation [2,3] for a large class of 2-connected bipartite planar graphs.", 
    "editor": [
      {
        "familyName": "Fleischer", 
        "givenName": "Rudolf", 
        "type": "Person"
      }, 
      {
        "familyName": "Xu", 
        "givenName": "Jinhui", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-68880-8_29", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-68865-5", 
        "978-3-540-68880-8"
      ], 
      "name": "Algorithmic Aspects in Information and Management", 
      "type": "Book"
    }, 
    "keywords": [
      "planar graphs", 
      "bipartite planar graphs", 
      "non-trivial size", 
      "contact representation", 
      "graph G", 
      "simple linear time algorithm", 
      "linear time algorithm", 
      "planar graph G", 
      "dual graph", 
      "large class", 
      "time algorithm", 
      "plane graph", 
      "graph", 
      "algorithm", 
      "representation", 
      "compact representation", 
      "st-orientations", 
      "multigraph", 
      "et al", 
      "vertices", 
      "grid", 
      "class", 
      "path", 
      "al", 
      "size", 
      "kind", 
      "length", 
      "segments", 
      "face", 
      "paper"
    ], 
    "name": "On Representation of Planar Graphs by Segments", 
    "pagination": "304-315", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052912391"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-68880-8_29"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-68880-8_29", 
      "https://app.dimensions.ai/details/publication/pub.1052912391"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:44", 
    "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_272.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-68880-8_29"
  }
]
 

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-68880-8_29'

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-68880-8_29'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-68880-8_29'

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-68880-8_29'


 

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

102 TRIPLES      23 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-68880-8_29 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nd2efa60a4f7d432398f7d87833890c4a
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description In this paper, we introduce Vertex-face contact representation (VFCR for short) for 2-connected plane multigraphs. We present a simple linear time algorithm for constructing a VFCR for 2-connected plane graphs. Our algorithm only uses an st-orientation for G and its corresponding st-orientation for the dual graph of G. We also show that one kind of vertex-vertex contact representation (VVCR) for 2-connected bipartite planar graphs introduced by Fraysseix et al. [2,3] can be easily obtained by applying our algorithm. In general, our algorithm produces a more compact representation than their algorithm.Then we investigate st-orientations for 3-connected planar graphs. We prove that a 3-connected planar graph G with n vertices and f faces, has an st-orientation with the length of its longest directed path \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\leq \frac{2n}{3}+2\lceil\sqrt{n/3}\rceil+5$\end{document}. This implies that such a graph G admits a VFCR in a grid with non-trivial size bound. This non-trivial size bound also applies to the vertex-vertex contact representation [2,3] for a large class of 2-connected bipartite planar graphs.
7 schema:editor N3bbd4a3ef6664fe49f22dc65d8cf3aaa
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8bb23e973d4543d985e902764d068763
12 schema:keywords al
13 algorithm
14 bipartite planar graphs
15 class
16 compact representation
17 contact representation
18 dual graph
19 et al
20 face
21 graph
22 graph G
23 grid
24 kind
25 large class
26 length
27 linear time algorithm
28 multigraph
29 non-trivial size
30 paper
31 path
32 planar graph G
33 planar graphs
34 plane graph
35 representation
36 segments
37 simple linear time algorithm
38 size
39 st-orientations
40 time algorithm
41 vertices
42 schema:name On Representation of Planar Graphs by Segments
43 schema:pagination 304-315
44 schema:productId Ne726d5f453744e72a5e01c7d95776fd3
45 Neeff30fba4b9418fa2b48c8633c77196
46 schema:publisher N27137419f1154067ae8c040eef9a90a4
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052912391
48 https://doi.org/10.1007/978-3-540-68880-8_29
49 schema:sdDatePublished 2022-05-20T07:44
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher Nc71885551fc14aaa9a03c77258d7c636
52 schema:url https://doi.org/10.1007/978-3-540-68880-8_29
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N27137419f1154067ae8c040eef9a90a4 schema:name Springer Nature
57 rdf:type schema:Organisation
58 N3bbd4a3ef6664fe49f22dc65d8cf3aaa rdf:first Nadc9fa3b10134c7c9dfacab8c8bea675
59 rdf:rest N512bf232c76b4377acd2f875d1bd3b11
60 N512bf232c76b4377acd2f875d1bd3b11 rdf:first N634c5e5ab1054364ba5913a4f97dfc06
61 rdf:rest rdf:nil
62 N634c5e5ab1054364ba5913a4f97dfc06 schema:familyName Xu
63 schema:givenName Jinhui
64 rdf:type schema:Person
65 N8bb23e973d4543d985e902764d068763 schema:isbn 978-3-540-68865-5
66 978-3-540-68880-8
67 schema:name Algorithmic Aspects in Information and Management
68 rdf:type schema:Book
69 Nadc9fa3b10134c7c9dfacab8c8bea675 schema:familyName Fleischer
70 schema:givenName Rudolf
71 rdf:type schema:Person
72 Nc71885551fc14aaa9a03c77258d7c636 schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 Nd2efa60a4f7d432398f7d87833890c4a rdf:first sg:person.015341066775.96
75 rdf:rest Nf1f5edf9e5c841eb8e8d2616242ea5ad
76 Ne726d5f453744e72a5e01c7d95776fd3 schema:name dimensions_id
77 schema:value pub.1052912391
78 rdf:type schema:PropertyValue
79 Neeff30fba4b9418fa2b48c8633c77196 schema:name doi
80 schema:value 10.1007/978-3-540-68880-8_29
81 rdf:type schema:PropertyValue
82 Nf1f5edf9e5c841eb8e8d2616242ea5ad rdf:first sg:person.012041227127.88
83 rdf:rest rdf:nil
84 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
85 schema:name Mathematical Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
88 schema:name Pure Mathematics
89 rdf:type schema:DefinedTerm
90 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
91 schema:familyName Zhang
92 schema:givenName Huaming
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
94 rdf:type schema:Person
95 sg:person.015341066775.96 schema:affiliation grid-institutes:grid.265893.3
96 schema:familyName Sadasivam
97 schema:givenName Sadish
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341066775.96
99 rdf:type schema:Person
100 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
101 schema:name Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
102 rdf:type schema:Organization
 




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


...