✦ LIBER ✦

Combinatorial curvature for planar graphs

✍ Scribed by Yusuke Higuchi

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 113 KB
Volume: 38
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10004

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Regarding an infinite planar graph G as a discrete analogue of a noncompact simply connected Riemannian surface, we introduce the combinatorial curvature of G corresponding to the sectional curvature of a manifold. We show this curvature has the property that its negative values are bounded above by a universal negative constant. We also prove that G is hyperbolic if its curvature is negative. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 220–229, 2001

📜 SIMILAR VOLUMES

A GRASP for graph planarization

✍ Resende, Mauricio G. C.; Ribeiro, Celso C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB 👁 2 views

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describe a GRASP for the graph planarization problem, extending the heuristic of Goldschmidt and Takvorian [ Networks 24 (1994) 69-73]. We review the basic concepts of GRASP: co

An algorithm for drawing planar graphs

✍ Bor Plestenjak 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 2 views

A simple algorithm for drawing 3-connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical s

Homomorphism bounds for oriented planar

Homomorphism bounds for oriented planar graphs

✍ T. H. Marshall 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

## Abstract If ${\cal C}$ is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a __homomorphism bound__ for ${\cal C}$ if there is a homomorphism from each graph in ${\cal C}$ to __H__. We find some necessary conditions for a graph to be a homomorphism bo

Faster Shortest-Path Algorithms for Plan

Faster Shortest-Path Algorithms for Planar Graphs

✍ Monika R Henzinger; Philip Klein; Satish Rao; Sairam Subramanian 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 445 KB

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we gi

On the delta-wye reduction for planar gr

On the delta-wye reduction for planar graphs

✍ K. Truemper 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB

We provide an elementary proof of an important theorem by G. V. Epifanov, according to which every two-terminal planar graph satisfying certain connectivity restrictions can by some sequence of series/parallel reductions and delta-wye exchanges be reduced to the graph consisting of the two terminals

A criterion for the planarity of a graph

✍ Jerome R. Breitenbach 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB 👁 1 views

In a recent paper, Carsten Thomassen [Carsten Thomassen, Planarity and duality of finite and infinite graphs. J. Combinatorial Theory Ser. B 29 (1980) 244-2711 has shown that a number of criteria for the planarity of a graph can be reduced to that of Kuratowski. Here we present another criterion whi