Optimal Graph Orientation with Storage Applications - Aichholzer, Aurenhammer, Rote (ResearchIndex)

Optimal Graph Orientation with Storage Applications (1995) (Make Corrections) (2 citations)
O. Aichholzer, F. Aurenhammer, Günter Rote

Home/Search Context Related

View or download:
cis.tugraz.ac.at/igi/oai...paper13.ps
Cached:  PS.gz  PS  PDF  DjVu  Image  Update  Help

From:  cis.tugraz.ac.at/igi/o...Welcome (more)
Homepages:  O.Aichholzer  F.Aurenhammer
  HPSearch  (Update Links)

Rate this article:

(best)
Comment on this article

(Enter summary)
Abstract: We show that the edges of a graph with maximum edge density d can always be oriented such that each vertex has in-degree at most d. Hence, for arbitrary graphs, edges can always be assigned to incident vertices as uniformly as possible. For example, in-degree 3 is achieved for planar graphs. This immediately gives a space-optimal data structure that answers edge membership queries in a maximum edge density-d graph in O(log d) time. 1 The Theorem Let G be an undirected graph with n vertices and ... (Update)

Context of citations to this paper: More

.... in order to bound the weight of GT (S) by means of the weights of the points in S after step k, we utilize the following result proved in [AAR]. Lemma 6 Let T be an arbitrary triangulation of S. Then the edges of T can be oriented such that each point p 2 S has an in degree of...

Cited by: More
Constant-Level Greedy Triangulations Approximate the MWT .. - Aichholzer.. (Correct)

Active bibliography (related documents): More All
2.1: Optimal Graph Orientation with Storage Applications - Aichholzer, Aurenhammer, Rote (1995) (Correct)
0.2: Edge-Critical Isometric Subgraphs of Hypercubes - Klavzar, Lipovec (2001) (Correct)
0.2: Fast Recognition Algorithms for Classes of Partial Cubes - Bostjan Bresar University (2001) (Correct)

Similar documents based on text: More All
0.8: Matchings between Intersecting Edges of Two.. - Aichholzer.. (1995) (Correct)
0.7: Triangulations Intersect Nicely - Aichholzer, Aurenhammer, Cheng.. (1996) (Correct)
0.7: Generalized Self-Approaching Curves - Aichholzer, Aurenhammer, Icking.. (1998) (Correct)

Related documents from co-citation: More All
2: Lower Bound for the Nonoptimality of the Greedy Triangulation (context) - Levcopoulos, Gamma - 1987
2: Fast greedy triangulation algorithms - Dickerson, Drysdale et al. - 1994
2: Triangulations Intersect Nicely - Aichholzer, Aurenhammer et al. - 1995

BibTeX entry: (Update)

O. Aichholzer, F. Aurenhammer, G. Rote, Optimal graph orientation with storage applications, SFB-Report F003-51 (Optimierung und Kontrolle), TU Graz, Austria, 1995. http://citeseer.nj.nec.com/article/aichholzer95optimal.html More

@misc{ aichholzer95optimal,
  author = "O. Aichholzer and F. Aurenhammer and G. Rote",
  title = "Optimal graph orientation with storage applications",
  text = "O. Aichholzer, F. Aurenhammer, G. Rote, Optimal graph orientation with
    storage applications, SFB-Report F003-51 (Optimierung und Kontrolle), TU
    Graz, Austria, 1995.",
  year = "1995",
  url = "citeseer.nj.nec.com/article/aichholzer95optimal.html" }

Citations (may not include all citations):
214 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
203 Data Structures and Network Algorithms (context) - Tarjan - 1987
134 algorithm for maximum matchings in bipartite graphs (context) - Hopcroft, Karp - 1973
68 Embedding planar graphs on the grid (context) - Schnyder - 1990
51 A linear algorithm for embedding planar graphs using PQ-tree.. (context) - Chiba, Nishizeki et al. - 1985
45 How to draw a planar graph on a grid (context) - de Fraysseix, Pach et al. - 1991
16 the embedding phase of the Hopcroft and Tarjan planarity tes.. - Mehlhorn, Mutzel
11 An Introductory Course (context) - Bollob'as, Theory - 1979
8 Data Structures and Efficient Algorithms (context) - Mehlhorn - 1984
4 Recognizing binary Hamming graphs in O (context) - Aurenhammer, Hagauer
2 Constant-level greedy triangulations approximate the MWT wel.. (context) - Aurenhammer, Aichholzer et al. - 1995
2 Combinatorial Theory B (context) - Garey, Graham et al. - 1975
2 Faster isometric embedding in products of complete graphs (context) - Aurenhammer, Formann et al. - 1994

Documents on the same site (http://www.cis.tu-graz.ac.at/igi/oaich/publications/Welcome.html): More
Matching Shapes with a Reference Point - Oswin Aichholzer, Helmut Alt.. (1994) (Correct)
Straight Skeletons for General Polygonal Figures in the Plane - Aichholzer, Aurenhammer (1996) (Correct)
Classifying Hyperplanes in Hypercubes (Extended Abstract) - Aichholzer, al. (Correct)

Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback