Plane Geometric Graph Augmentation: A Generic Perspective

Ferran Hurtado () and Csaba D. Tóth ()
Additional contact information
Ferran Hurtado: Universitat Politècnica de Catalunya (UPC), Departament de Matemàtica Aplicada II
Csaba D. Tóth: University of Calgary, Department of Mathematics and Statistics

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 327-354 from Springer

Abstract: Abstract Graph augmentation problems are motivated by network design and have been studied extensively in optimization. We consider augmentation problems over plane geometric graphs, that is, graphs given with a crossing-free straight-line embedding in the plane. The geometric constraints on the possible new edges render some of the simplest augmentation problems intractable, and in many cases only extremal results are known. We survey recent results, highlight common trends, and gather numerous conjectures and open problems.

Keywords: Planar Graph; Hamiltonian Cycle; Geometric Graph; Congestion Game; Stretch Factor (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_17

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_17

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().