Combinatorics of planar maps and algorithmic applications.

Abstract : This thesis describes algorithms on planar maps (graphs embedded in the plane without edge-crossings) based on their combinatorial properties. For several important families of planar maps (3-connected, triangulations, quadran- gulations), efficient procedures of random generation, encoding, and straight-line drawing are described. In particular, the first optimal encoder for the combinatorial incidences of polygonal meshes with spherical topology is developed. Starting from a generator for 3-connected maps, a new random generator for planar graphs is in- troduced. The complexity of generation is the best currently known: quadratic (in expectation) for exact-size sampling and linear (in expectation) for approximate- size sampling. Finally, several straight-line drawing algorithms for planar maps are introduced. The procedures are both simple to describe and very efficient, yielding the best known grid size for two families of maps: triangulations of the 4-gon with no filled 3-cycle —called irreducible— and quadrangulations. The algo- rithms presented in the thesis take advantage of several combinatorial structures on planar maps (orientations, partitions into spanning trees) as well as new bijective constructions
Mots-clés : Cartes planaires
Document type :
Theses
Complete list of metadatas

Cited literature [104 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00002931
Contributor : Ecole Polytechnique <>
Submitted on : Tuesday, July 27, 2010 - 9:02:56 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on : Thursday, October 28, 2010 - 4:53:03 PM

File

Identifiers

  • HAL Id : pastel-00002931, version 1

Collections

Citation

Fusy Eric. Combinatorics of planar maps and algorithmic applications.. Computer Science [cs]. Ecole Polytechnique X, 2007. English. ⟨pastel-00002931⟩

Share

Metrics

Record views

289

Files downloads

351