Name
Abstract | ||
|---|---|---|
In random geometric graphs, vertices are randomly distributed on [0, 1]2 and pairs of vertices are connected by edges whenever they are sufficiently close together. Layout problems seek a linear ordering of the vertices of a graph such that a certain measure is minimized. In this paper, we study several layout problems on random geometric graphs: Bandwidth, Minimum Linear Arrangement, Minimum Cut, Minimum Sum Cut, Vertex Separation and Bisection. We first prove that some of these problems remain NP-complete even for geometric graphs. Afterwards, we compute lower bounds that hold with high probability on random geometric graphs. Finally, we characterize the probabilistic behavior of the lexicographic ordering for our layout problems on the class of random geometric graphs. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/3-540-46784-X_28 | WG |
Keywords | Field | DocType |
layout problem,random geometric graph,vertex separation,high probability,random geometric graphs,minimum sum cut,geometric graph,minimum linear arrangement,certain measure,linear orderings,lower bound,minimum cut,linear order,lexicographic order | Geometric graph theory,Discrete mathematics,Random regular graph,Combinatorics,Modular decomposition,Indifference graph,Random graph,Spatial network,Chordal graph,Metric dimension,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-66731-8 | 1 | 0.50 |
References | Authors | |
13 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 489 | 204.59 |
| Mathew D. Penrose | 2 | 249 | 28.21 |
| Jordi Petit | 3 | 89 | 10.89 |
| Maria J. Serna | 4 | 473 | 70.53 |