# Drawing planar graphs using the canonical ordering

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

1996-07

AUTHORS ABSTRACT

We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices.Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid.Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree. Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices. Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends. Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid. Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included. More... »

PAGES

4-32

### References to SciGraph publications

• 1995. On the computational complexity of upward and rectilinear planarity testing in GRAPH DRAWING
• 1994. Two algorithms for finding rectangular duals of planar graphs in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
• 1988-11. A linear algorithm to find a rectangular dual of a planar triangulated graph in ALGORITHMICA
• 1994. Planar drawings and angular resolution: Algorithms and bounds in ALGORITHMS — ESA '94
• 1994. A more compact visibility representation in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
• 1993. Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract) in ALGORITHMS AND DATA STRUCTURES
• 1993. Parallel construction of canonical ordering and convex drawing of triconnected planar graphs in ALGORITHMS AND COMPUTATION
• 1986-12. Rectilinear planar layouts and bipolar orientations of planar graphs in DISCRETE & COMPUTATIONAL GEOMETRY
• 1986-12. A unified approach to visibility representations of planar graphs in DISCRETE & COMPUTATIONAL GEOMETRY
• 1992-04. Area requirement and symmetry display of planar upward drawings in DISCRETE & COMPUTATIONAL GEOMETRY
• 1990-03. How to draw a planar graph on a grid in COMBINATORICA
• 1993. Hexagonal grid drawings in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
• 1992-04. Theoretical results on at most 1-bend embeddability of graphs in ACTA MATHEMATICAE APPLICATAE SINICA, ENGLISH SERIES
• 1985-06. Drawing plane graphs nicely in ACTA INFORMATICA

TITLE

Algorithmica

ISSUE

1

VOLUME

16

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02086606

DOI

http://dx.doi.org/10.1007/bf02086606

DIMENSIONS

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

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/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Utrecht University",
"id": "https://www.grid.ac/institutes/grid.5477.1",
"name": [
"Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands"
],
"type": "Organization"
},
"familyName": "Kant",
"givenName": "G.",
"id": "sg:person.013743554756.94",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013743554756.94"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/bf01762117",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003139574",
"https://doi.org/10.1007/bf01762117"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01762117",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003139574",
"https://doi.org/10.1007/bf01762117"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-57155-8_244",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005416239",
"https://doi.org/10.1007/3-540-57155-8_244"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02122694",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005926153",
"https://doi.org/10.1007/bf02122694"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02122694",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005926153",
"https://doi.org/10.1007/bf02122694"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02122694",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005926153",
"https://doi.org/10.1007/bf02122694"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187706",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008881195",
"https://doi.org/10.1007/bf02187706"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187706",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008881195",
"https://doi.org/10.1007/bf02187706"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187706",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008881195",
"https://doi.org/10.1007/bf02187706"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-57899-4_70",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012839777",
"https://doi.org/10.1007/3-540-57899-4_70"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0095-8956(80)90083-0",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016550143"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-57899-4_69",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018910920",
"https://doi.org/10.1007/3-540-57899-4_69"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/321850.321852",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023277958"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/net.3230140202",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023775252"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187705",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027312329",
"https://doi.org/10.1007/bf02187705"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187705",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027312329",
"https://doi.org/10.1007/bf02187705"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0022-0000(76)80045-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030334487"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0022-0000(85)90004-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030929286"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-58950-3_384",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031098794",
"https://doi.org/10.1007/3-540-58950-3_384"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0049393",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031647520",
"https://doi.org/10.1007/bfb0049393"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1090/s0002-9939-1951-0041425-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032762886"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02006154",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035226061",
"https://doi.org/10.1007/bf02006154"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02006154",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035226061",
"https://doi.org/10.1007/bf02006154"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0304-3975(76)90086-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035496339"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-57568-5_261",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039080031",
"https://doi.org/10.1007/3-540-57568-5_261"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1112/plms/s3-13.1.743",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1040536272"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/142675.142728",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041197738"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-56402-0_53",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043848821",
"https://doi.org/10.1007/3-540-56402-0_53"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0304-3975(92)90349-k",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044028443"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0925-7721(94)00014-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049116874"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1112/plms/s3-10.1.304",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051445647"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0020-0190(91)90059-q",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052090013"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf00264230",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052102689",
"https://doi.org/10.1007/bf00264230"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf00264230",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052102689",
"https://doi.org/10.1007/bf00264230"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187850",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053554536",
"https://doi.org/10.1007/bf02187850"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187850",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053554536",
"https://doi.org/10.1007/bf02187850"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/31.1746",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061152809"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/31.34669",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061153032"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0202012",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062841200"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0216030",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062841976"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0222063",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062842466"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0222072",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062842475"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/s0895480193242931",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062882900"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1142/s0218195997000144",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062960880"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/sfcs.1989.63515",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1086220172"
],
"type": "CreativeWork"
}
],
"datePublished": "1996-07",
"datePublishedReg": "1996-07-01",
"description": "We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n\u22124)\u00d7(n\u22122) grid, wheren is the number of vertices.Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann\u00d7n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]\u00d7[n/2] grid.Every triconnected planar graphG admits a planar polyline grid drawing on a (2n\u22126)\u00d7(3n\u22129) grid with minimum angle larger than 2/d radians and at most 5n\u221215 bends, withd the maximum degree. Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n\u22124)\u00d7(n\u22122) grid, wheren is the number of vertices. Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann\u00d7n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends. Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]\u00d7[n/2] grid. Every triconnected planar graphG admits a planar polyline grid drawing on a (2n\u22126)\u00d7(3n\u22129) grid with minimum angle larger than 2/d radians and at most 5n\u221215 bends, withd the maximum degree. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.",
"genre": "research_article",
"id": "sg:pub.10.1007/bf02086606",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"name": "Drawing planar graphs using the canonical ordering",
"pagination": "4-32",
"productId": [
{
"type": "PropertyValue",
"value": [
"736dc031e71a8a2d543144df1e046b14b0b28c422ab2028d266cd16efc2ef6df"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/bf02086606"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1024228802"
]
}
],
"sameAs": [
"https://doi.org/10.1007/bf02086606",
"https://app.dimensions.ai/details/publication/pub.1024228802"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T11:56",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29215_00000001.jsonl",
"type": "ScholarlyArticle",
}
]``````

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/bf02086606'`

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/bf02086606'`

`curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02086606'`

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

`curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02086606'`

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

183 TRIPLES      21 PREDICATES      63 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
4 schema:citation sg:pub.10.1007/3-540-56402-0_53
5 sg:pub.10.1007/3-540-57155-8_244
6 sg:pub.10.1007/3-540-57568-5_261
7 sg:pub.10.1007/3-540-57899-4_69
8 sg:pub.10.1007/3-540-57899-4_70
9 sg:pub.10.1007/3-540-58950-3_384
10 sg:pub.10.1007/bf00264230
11 sg:pub.10.1007/bf01762117
12 sg:pub.10.1007/bf02006154
13 sg:pub.10.1007/bf02122694
14 sg:pub.10.1007/bf02187705
15 sg:pub.10.1007/bf02187706
16 sg:pub.10.1007/bf02187850
17 sg:pub.10.1007/bfb0049393
18 https://doi.org/10.1002/net.3230140202
19 https://doi.org/10.1016/0020-0190(91)90059-q
20 https://doi.org/10.1016/0022-0000(85)90004-2
21 https://doi.org/10.1016/0095-8956(80)90083-0
22 https://doi.org/10.1016/0304-3975(76)90086-4
23 https://doi.org/10.1016/0304-3975(92)90349-k
24 https://doi.org/10.1016/0925-7721(94)00014-x
25 https://doi.org/10.1016/s0022-0000(76)80045-1
26 https://doi.org/10.1090/s0002-9939-1951-0041425-5
27 https://doi.org/10.1109/31.1746
28 https://doi.org/10.1109/31.34669
29 https://doi.org/10.1109/sfcs.1989.63515
30 https://doi.org/10.1112/plms/s3-10.1.304
31 https://doi.org/10.1112/plms/s3-13.1.743
32 https://doi.org/10.1137/0202012
33 https://doi.org/10.1137/0216030
34 https://doi.org/10.1137/0222063
35 https://doi.org/10.1137/0222072
36 https://doi.org/10.1137/s0895480193242931
37 https://doi.org/10.1142/s0218195997000144
38 https://doi.org/10.1145/142675.142728
39 https://doi.org/10.1145/321850.321852
40 schema:datePublished 1996-07
41 schema:datePublishedReg 1996-07-01
42 schema:description We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices.Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid.Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree. Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices. Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends. Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid. Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.
43 schema:genre research_article
44 schema:inLanguage en
45 schema:isAccessibleForFree true
46 schema:isPartOf N0b3c97f6396343d5a834996c550a28ae
47 N3d8414ae25fe438482bb72ee978dd2e2
48 sg:journal.1047644
49 schema:name Drawing planar graphs using the canonical ordering
50 schema:pagination 4-32
51 schema:productId N560fb2c5afcb46619716a6c27b1e24e5
52 N94a7b62c89aa428c8719f0dea781270b
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024228802
55 https://doi.org/10.1007/bf02086606
56 schema:sdDatePublished 2019-04-11T11:56
61 sgo:sdDataset articles
62 rdf:type schema:ScholarlyArticle
64 rdf:type schema:PublicationVolume
65 N3d8414ae25fe438482bb72ee978dd2e2 schema:issueNumber 1
66 rdf:type schema:PublicationIssue
68 rdf:rest rdf:nil
69 N560fb2c5afcb46619716a6c27b1e24e5 schema:name doi
70 schema:value 10.1007/bf02086606
71 rdf:type schema:PropertyValue
73 schema:value 736dc031e71a8a2d543144df1e046b14b0b28c422ab2028d266cd16efc2ef6df
74 rdf:type schema:PropertyValue
75 Neb19edca95cd4437b1ecd87eada11d19 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
78 schema:value pub.1024228802
79 rdf:type schema:PropertyValue
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:journal.1047644 schema:issn 0178-4617
87 1432-0541
88 schema:name Algorithmica
89 rdf:type schema:Periodical
90 sg:person.013743554756.94 schema:affiliation https://www.grid.ac/institutes/grid.5477.1
91 schema:familyName Kant
92 schema:givenName G.
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013743554756.94
94 rdf:type schema:Person
95 sg:pub.10.1007/3-540-56402-0_53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043848821
96 https://doi.org/10.1007/3-540-56402-0_53
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/3-540-57155-8_244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005416239
99 https://doi.org/10.1007/3-540-57155-8_244
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/3-540-57568-5_261 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039080031
102 https://doi.org/10.1007/3-540-57568-5_261
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/3-540-57899-4_69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018910920
105 https://doi.org/10.1007/3-540-57899-4_69
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/3-540-57899-4_70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012839777
108 https://doi.org/10.1007/3-540-57899-4_70
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/3-540-58950-3_384 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031098794
111 https://doi.org/10.1007/3-540-58950-3_384
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/bf00264230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052102689
114 https://doi.org/10.1007/bf00264230
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/bf01762117 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003139574
117 https://doi.org/10.1007/bf01762117
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/bf02006154 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035226061
120 https://doi.org/10.1007/bf02006154
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/bf02122694 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005926153
123 https://doi.org/10.1007/bf02122694
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/bf02187705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027312329
126 https://doi.org/10.1007/bf02187705
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/bf02187706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008881195
129 https://doi.org/10.1007/bf02187706
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/bf02187850 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053554536
132 https://doi.org/10.1007/bf02187850
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/bfb0049393 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031647520
135 https://doi.org/10.1007/bfb0049393
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1002/net.3230140202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023775252
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1016/0020-0190(91)90059-q schema:sameAs https://app.dimensions.ai/details/publication/pub.1052090013
140 rdf:type schema:CreativeWork
141 https://doi.org/10.1016/0022-0000(85)90004-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030929286
142 rdf:type schema:CreativeWork
143 https://doi.org/10.1016/0095-8956(80)90083-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016550143
144 rdf:type schema:CreativeWork
145 https://doi.org/10.1016/0304-3975(76)90086-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035496339
146 rdf:type schema:CreativeWork
147 https://doi.org/10.1016/0304-3975(92)90349-k schema:sameAs https://app.dimensions.ai/details/publication/pub.1044028443
148 rdf:type schema:CreativeWork
149 https://doi.org/10.1016/0925-7721(94)00014-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1049116874
150 rdf:type schema:CreativeWork
151 https://doi.org/10.1016/s0022-0000(76)80045-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030334487
152 rdf:type schema:CreativeWork
153 https://doi.org/10.1090/s0002-9939-1951-0041425-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032762886
154 rdf:type schema:CreativeWork
155 https://doi.org/10.1109/31.1746 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061152809
156 rdf:type schema:CreativeWork
157 https://doi.org/10.1109/31.34669 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061153032
158 rdf:type schema:CreativeWork
159 https://doi.org/10.1109/sfcs.1989.63515 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086220172
160 rdf:type schema:CreativeWork
161 https://doi.org/10.1112/plms/s3-10.1.304 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051445647
162 rdf:type schema:CreativeWork
163 https://doi.org/10.1112/plms/s3-13.1.743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040536272
164 rdf:type schema:CreativeWork
165 https://doi.org/10.1137/0202012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841200
166 rdf:type schema:CreativeWork
167 https://doi.org/10.1137/0216030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841976
168 rdf:type schema:CreativeWork
169 https://doi.org/10.1137/0222063 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842466
170 rdf:type schema:CreativeWork
171 https://doi.org/10.1137/0222072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842475
172 rdf:type schema:CreativeWork
173 https://doi.org/10.1137/s0895480193242931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882900
174 rdf:type schema:CreativeWork
175 https://doi.org/10.1142/s0218195997000144 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062960880
176 rdf:type schema:CreativeWork
177 https://doi.org/10.1145/142675.142728 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041197738
178 rdf:type schema:CreativeWork
179 https://doi.org/10.1145/321850.321852 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023277958
180 rdf:type schema:CreativeWork
181 https://www.grid.ac/institutes/grid.5477.1 schema:alternateName Utrecht University
182 schema:name Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands
183 rdf:type schema:Organization