Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
GeoInformatica
Published in: GeoInformatica 4/2018

29-09-2018

Generating random connected planar graphs

Author: Daniel A. Griffith

Published in: GeoInformatica | Issue 4/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Connected planar graphs are of interest to a variety of scholars. Being able to simulate a database of such graphs with selected properties would support specific types of inference for spatial analysis and other network-based disciplines. This paper presents a simple, efficient, and flexible connected planar graph generator for this purpose. It also summarizes a comparison between an empirical set of specimen graphs and their simulated counterpart set, and establishes evidence for positing a conjecture about the principal eigenvalue of connected planar graphs. Finally, it summarizes a probability assessment of the algorithm’s outcomes as well as a comparison between the new algorithm and selected existing planar graph generators.
previous article Continuous k nearest neighbor queries over large multi-attribute trajectories: a systematic approach
next article Editorial: Advances in spatial and temporal databases

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
This upper bound on n is a restriction set by the Fortran compiler used. It can be relaxed by changing the computer software for implementation (see supplementary material for the Fortran code).
 
Literature
1.
Bodirsky M, Gröpl C, Kang M (2007) Generating labeled planar graphs uniformly at random. Theor Comput Sci 379:377–386CrossRef
2.
S. Meinert and D. Wagner, (2011) An experimental study on generating planar graphs, Karlsruhe Reports in Informatics,13, Karlsruhe Institute of Technology, Faculty of Informatics Karlsruhe, Germany, 2011
3.
Osthus D, Prömel H, Taraz A (2003) On random planar graphs, the number of planar graphs and their triangulations. Journal of Combinatorial Theory, Series B 88:119–134CrossRef
4.
Bonichon N, Gavoille C, Hanusse N, Poulalhon D, Schaeffer G (2006) Planar graphs, via well-orderly maps and trees. Graphs and Combinatorics 22:185–202CrossRef
5.
O. Giménez and M. Noy. “The number of planar graphs and properties of random planar graphs,” Proceedings of the 2005 International Conference on Analysis of Algorithms C. Saunders, M. Grobelnik, S. Gunn, and J. Shawe-Taylor (editors), Springer-Verlag, Berlin (2005) pp. 147–156
6.
R. Read and R. Wilson (2005) An Atlas of Graphs, Clarendon press, Gloucestershire, England
7.
Geographical Analysis, (2011) Issue 4, 43, 345–435
8.
Fortin M-J, James P, MacKenzie A, Melles S, Rayfield B (2012) Spatial statistics, spatial regression, and graph theory in economy. Spat Stat 1:100–109CrossRef
9.
Boots B, Royal G (1991) A conjecture on the maximum value of the principal eigenvalue of a planar graph. Geogr Anal 23:276–282CrossRef
10.
M. Tait and J. Tobin, (2016) Three conjectures in extremal spectral graph theory, arXiv:​1606.​01916v1 [math.CO], last accessed on 15 December 2016
11.
Páez A, Scott D, Volz E (2008) Weight matrices for social influence analysis: an investigation of measurement errors and their effect on model identification and estimation quality. Soc Networks 30:300–317CrossRef
12.
Griffith D (2017) Some robust assessments of Moran eigenvector spatial filtering. Spatial Statistics 22:155–179CrossRef
13.
Masucci A, Smith D, Crooks A, Batty M (2009) Random planar graphs and the London street network. The European Physical Journal B 71:259–271CrossRef
14.
Ermagun A, Levinson D (2018) An introduction to the network weight matrix. Geogr Anal 50:76–96CrossRef
15.
16.
S. Arlinghaus, W. Arlinghaus, and F. Harary. (2002) Graph Theory and Geography: An Interactive View, Wiley, New York
17.
18.
E. Allender and M. Mahajan, The complexity of planarity testing. Inf Comput 189 (2004), 117–134CrossRef
19.
F. Harary and E. Palmer. 1973. Graphical enumeration. NY: Academic Press
20.
Griffith D, Sone A (1995) Trade-offs associated with normalizing constant computational simplifications for estimating spatial statistical models. J Stat Comput Simul 51:165–183CrossRef
21.
Griffith D (2000) Eigenfunction properties and approximations of selected incidence matrices employed in spatial analyses. Linear Algebra Appl 321:95–112CrossRef
22.
Wilf H (1967) The eigenvalues of a graph and its chromatic number. J Lond Math Soc 42:330–332CrossRef
23.
Hoffman A (1970) “On eigenvalues and colorings of graphs,” Graph Theory and Its Applications H. Bernard (editor). Academic Press, New York, pp 79–92
24.
25.
26.
Anderson T (1963) Asymptotic theory for principal components analysis. Ann Math Stat 34:122–148CrossRef
27.
Johnstone I (2001) On the distribution of the largest eigenvalue in principal components analysis. Ann Stat 29:295–327CrossRef
Metadata
Title
Generating random connected planar graphs
Author
Daniel A. Griffith
Publication date
29-09-2018
Publisher
Springer US
Published in
GeoInformatica / Issue 4/2018
Print ISSN: 1384-6175
Electronic ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-018-0328-3

Other articles of this Issue 4/2018

GeoInformatica 4/2018 Go to the issue

OriginalPaper

Mining mobile application usage pattern for demand prediction by considering spatial and temporal relations

Correction

Correction to: A framework for annotating OpenStreetMap objects using geo-tagged tweets

OriginalPaper

k-most suitable locations selection

OriginalPaper

Location-aware query reformulation for search engines

OriginalPaper

ST-Hadoop: a MapReduce framework for spatio-temporal data

OriginalPaper

Diverse nearest neighbors queries using linear skylines