Random planar graphs with n nodes and a fixed number of edges.

Random planar graphs with n nodes and a fixed number of edges.

Let ℘(n, m) be the class of simple labelled planar graphs with n nodes and m edges, and let Rn,q be a graph drawn uniformly at random from ℘(n, ⌊qn⌋). We show properties that hold with high probability (w.h.p.) for Rn,q when 1 < q < 3. For example, we show that Rn,q contains w.h.p. lin...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Gerke, S, McDiarmid, C, Steger, A, Weißl, A
Fformat:	Conference item
Cyhoeddwyd:	SIAM 2005

Eitemau Tebyg

On the Number of Edges in Random Planar Graphs.
gan: Gerke, S, et al.
Cyhoeddwyd: (2004)

Random planar graphs
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2005)

Random planar graphs.
gan: Mcdiarmid, C, et al.
Cyhoeddwyd: (2005)

On the Maximum Degree of a Random Planar Graph.
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2008)

Random cubic planar graphs.
gan: Bodirsky, M, et al.
Cyhoeddwyd: (2007)

On the chromatic number of random geometric graphs
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2011)

On the chromatic number of random geometric graphs
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2011)

The t-improper chromatic number of random graphs
gan: Kang, R, et al.
Cyhoeddwyd: (2008)

The t-Improper Chromatic Number of Random Graphs
gan: Kang, R, et al.
Cyhoeddwyd: (2010)

Graph Imperfection.
gan: Gerke, S, et al.
Cyhoeddwyd: (2001)

The t-stability number of a random graph
gan: Fountoulakis, N, et al.
Cyhoeddwyd: (2008)

Graph Imperfection II.
gan: Gerke, S, et al.
Cyhoeddwyd: (2001)

The number of disk graphs
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2014)

The number of disk graphs.
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2014)

Edge-maximal graphs on surfaces
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2017)

Uniform multicommodity flow through the complete graph with random edge-capacities.
gan: Aldous, D, et al.
Cyhoeddwyd: (2009)

Graph Imperfection with a Co-Site Constraint.
gan: Gerke, S, et al.
Cyhoeddwyd: (2004)

Random graphs on surfaces.
gan: McDiarmid, C
Cyhoeddwyd: (2008)

List Colouring Squares of Planar Graphs
gan: Havet, F, et al.
Cyhoeddwyd: (2008)

The Number of Bits Needed to Represent a Unit Disk Graph.
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2010)

Random perfect graphs
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2018)

Random Graphs from a Minor-Closed Class.
gan: McDiarmid, C
Cyhoeddwyd: (2009)

Bisecting sparse random graphs.
gan: Luczak, M, et al.
Cyhoeddwyd: (2001)

Random graphs from a weighted minor-closed class
gan: McDiarmid, C
Cyhoeddwyd: (2012)

Connectivity for random graphs from a weighted bridge-addable class
gan: McDiarmid, C
Cyhoeddwyd: (2012)

The number of planar graphs and properties of random planar graphs
gan: Omer Gimenez, et al.
Cyhoeddwyd: (2005-01-01)

Random graphs with few disjoint cycles
gan: Kurauskas, V, et al.
Cyhoeddwyd: (2010)

Modularity in random regular graphs and lattices.
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2013)

Modularity of Erdos-Rényi random graphs
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2018)

Random graphs from a block-stable class
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2016)

The Number of Edges in k-Quasi-planar Graphs
gan: Fox, Jacob, et al.
Cyhoeddwyd: (2013)

On the spread of random graphs
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2014)

On the spread of random graphs
gan: Addario-Berry, L, et al.
Cyhoeddwyd: (2009)

Random unlabelled graphs containing few disjoint cycles.
gan: Kang, M, et al.
Cyhoeddwyd: (2011)

Random Graphs Containing Few Disjoint Excluded Minors
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2014)

Uniform multicommodity flows in the hypercube with random edge‐capacities
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2016)

Upper bounds on the non-3-colourability threshold of random graphs.
gan: Fountoulakis, N, et al.
Cyhoeddwyd: (2002)

Largest sparse subgraphs of random graphs.
gan: Fountoulakis, N, et al.
Cyhoeddwyd: (2011)

Largest sparse subgraphs of random graphs
gan: Fountoulakis, N, et al.
Cyhoeddwyd: (2014)

Clique colouring of binomial random graphs
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2018)