@prefix ns1: .
@prefix ns2: .
@prefix rdf: .
@prefix rdfs: .
@prefix xml: .
@prefix xsd: .
a ns1:ScholarlyArticle ;
ns1:about ,
;
ns1:author ( ) ;
ns1:datePublished "2005-01-14" ;
ns1:datePublishedReg "2005-01-14" ;
ns1:description """Abstract
We study the properties of Schnyder’s realizers and canonical ordering trees of plane graphs. Based on these newly
discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First, we show that G has a
visibility representation with height at most ⌈ 15n/16 ⌉. This improves the previous best bound
of (n - 1). Second, we show that every plane graph G has a straight-line grid
embedding on an (n - δ0 - 1) × (n - δ0 - 1) grid, where δ0 is the number of cyclic faces of G with respect to its
minimum realizer. This improves the previous best bound of (n - 1) × (n - 1).
We also study the properties of the regular edge labeling of 4-connected plane triangulation. Based on these
properties, we show that every such a graph has a canonical ordering tree with at most ⌈ (n + 1)/2 ⌉ leaves.
This improves the previously known bound of ⌊ (2n + 1)/3 ⌋.
We show that every 4-connected plane graph has a visibility
representation with height at most ⌈ 3n/4 ⌉.
All drawings discussed in this paper can be obtained in linear time.""" ;
ns1:genre "article" ;
ns1:inLanguage "en" ;
ns1:isAccessibleForFree true ;
ns1:isPartOf [ a ns1:PublicationIssue ;
ns1:issueNumber "2" ],
[ a ns1:PublicationVolume ;
ns1:volumeNumber "33" ],
;
ns1:keywords "Schnyder’s realizers",
"applications",
"canonical ordering tree",
"compact drawings",
"cyclic faces",
"drawings",
"edge labeling",
"face",
"graph",
"graph G",
"graph drawing",
"grid",
"height",
"labeling",
"leaves",
"linear time",
"minimum realizer",
"number",
"ordering trees",
"paper",
"plane graph",
"plane graph G",
"plane triangulations",
"properties",
"realizers",
"regular edge labeling",
"representation",
"respect",
"straight-line grid",
"style",
"time",
"trees",
"triangulation",
"vertices",
"visibility",
"visibility representation",
"Δ0" ;
ns1:name "Canonical Ordering Trees and Their Applications in Graph Drawing" ;
ns1:pagination "321-344" ;
ns1:productId [ a ns1:PropertyValue ;
ns1:name "doi" ;
ns1:value "10.1007/s00454-004-1154-y" ],
[ a ns1:PropertyValue ;
ns1:name "dimensions_id" ;
ns1:value "pub.1021220162" ] ;
ns1:sameAs ,
;
ns1:sdDatePublished "2022-01-01T18:14" ;
ns1:sdLicense "https://scigraph.springernature.com/explorer/license/" ;
ns1:sdPublisher [ a ns1:Organization ;
ns1:name "Springer Nature - SN SciGraph project" ] ;
ns1:url "https://doi.org/10.1007/s00454-004-1154-y" ;
ns2:license ;
ns2:sdDataset "articles" .
a ns1:DefinedTerm ;
ns1:inDefinedTermSet ;
ns1:name "Mathematical Sciences" .
a ns1:DefinedTerm ;
ns1:inDefinedTermSet ;
ns1:name "Pure Mathematics" .
a ns1:Periodical ;
ns1:issn "0179-5376",
"1432-0444" ;
ns1:name "Discrete & Computational Geometry" ;
ns1:publisher "Springer Nature" .
a ns1:Person ;
ns1:affiliation ;
ns1:familyName "He" ;
ns1:givenName "Xin" ;
ns1:sameAs .
a ns1:Person ;
ns1:affiliation ;
ns1:familyName "Zhang" ;
ns1:givenName "Huaming" ;
ns1:sameAs .
a ns1:Organization ;
ns1:alternateName "Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA" ;
ns1:name "Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA" .