45:
1042:
908:
is a graph formed from the triangulations of a point set, in which each vertex represents a triangulation and two triangulations are connected by an edge if they differ by the replacement of one edge for another. It is also possible to define related flip graphs for partitions into quadrilaterals or
830:
is a graph in which each vertex is associated with a set and in which vertices are connected by edges whenever the corresponding sets have a nonempty intersection. When the sets are geometric objects, the result is a geometric graph. For instance, the intersection graph of line segments in one
873:
of a closed polygon connects each pair of vertices by an edge whenever the line segment connecting the vertices lies entirely in the polygon. It is not known how to test efficiently whether an undirected graph can be represented as a visibility graph.
897:, a graph in which vertices represent permutations of a set of ordered objects and edges represent swaps of objects adjacent in the order. Several other important classes of graphs including
889:
between the corresponding hypercube vertices. Many important families of combinatorial structures, such as the acyclic orientations of a graph or the adjacencies between regions in a
799:
is a graph in which the vertices represent points in the plane, and each edge is assigned the length equal to the
Euclidean distance between its endpoints. The
758:, a graph defined from a set of points in the plane by connecting two points with an edge whenever there exists a circle containing only those two points.
754:
is a planar straight line graph to which no more edges may be added, so called because every face is necessarily a triangle; a special case of this is the
561:
773:
is the set of vertices and edges of said polyhedron or polytope. The skeleton of any convex polyhedron is a planar graph, and the skeleton of any
788:
states that any 3-connected planar graph is the skeleton of a convex polyhedron; for this reason, this class of graphs is also known as the
909:
pseudotriangles, and for higher-dimensional triangulations. The flip graph of triangulations of a convex polygon forms the skeleton of the
854:
of a family of points and lines has a vertex for each of these objects and an edge for every incident point-line pair. The Levi graphs of
668:
1046:
1018:
716:; thus, it can be described as "the theory of geometric and topological graphs" (Pach 2013). Geometric graphs are also known as
847:(proven in 2009) states that every planar graph can be represented as the intersection graph of line segments in the plane.
921:
of a point set (projections of higher-dimensional convex hulls) can also be represented as a skeleton, of the so-called
918:
551:
280:
625:
208:
1062:
800:
521:
893:, can be represented as partial cube graphs. An important special case of a partial cube is the skeleton of the
511:
506:
661:
620:
137:
689:
466:
310:
257:
72:
501:
844:
816:
730:
630:
536:
531:
496:
295:
193:
132:
218:
958:
934:
855:
778:
654:
556:
516:
23:
414:
751:
637:
456:
223:
157:
112:
890:
840:
755:
541:
526:
441:
804:
785:
713:
642:
461:
431:
320:
275:
989:. Bolyai Soc. Math. Stud. Vol. 25. Budapest: János Bolyai Math. Soc. pp. 465–484.
1002:
843:
states that the intersection graphs of non-crossing circles are exactly the planar graphs.
409:
290:
743:
8:
968:. Contemporary Mathematics. Vol. 453. American Mathematical Society. pp. 49–86.
863:
815:
is formed by connecting pairs of points that are a unit distance apart in the plane. The
812:
762:
446:
315:
305:
300:
152:
97:
87:
811:. It is also possible to define graphs by conditions on the distances; in particular, a
1025:. Washington, DC: Mathematical Association of America. pp. 174–194. Archived from
827:
285:
238:
213:
102:
92:
1026:
914:
709:
582:
248:
198:
107:
82:
1010:
990:
886:
870:
820:
789:
341:
330:
228:
188:
172:
901:
have related definitions involving metric embeddings (Bandelt & Chepoi 2008).
998:
994:
944:
859:
836:
735:
717:
705:
701:
577:
358:
233:
142:
77:
31:
1014:
939:
832:
808:
712:, where the edges are allowed to be arbitrary continuous curves connecting the
587:
393:
368:
363:
337:
326:
203:
167:
162:
122:
60:
1056:
910:
894:
697:
546:
451:
436:
378:
127:
117:
973:
898:
881:
is a graph for which the vertices can be associated with the vertices of a
878:
747:
739:
685:
491:
388:
243:
700:
and geometric properties of geometric graphs, meaning graphs drawn in the
980:. Contemporary Mathematics. Vol. 342. American Mathematical Society.
905:
851:
766:
426:
383:
373:
882:
693:
591:
147:
44:
966:
Surveys on
Discrete and Computational Geometry - Twenty Years Later
770:
985:
Pach, János (2013). "The beginnings of geometric graph theory".
1041:
734:
is a graph in which the vertices are embedded as points in the
1009:
696:
means. In a stricter sense, geometric graph theory studies
684:
in the broader sense is a large and amorphous subfield of
835:; the intersection graph of unit disks in the plane is a
750:
may be represented as a planar straight line graph. A
723:
885:, in such a way that distance in the graph equals
1054:
957:Bandelt, Hans-JĂĽrgen; Chepoi, Victor (2008).
956:
738:, and the edges are embedded as non-crossing
662:
1023:Geometry at Work: Papers in Applied Geometry
959:"Metric graph theory and geometry: a survey"
1019:"Bridges between geometry and graph theory"
669:
655:
704:with possibly intersecting straight-line
1055:
984:
978:Towards a Theory of Geometric Graphs
972:
724:Different types of geometric graphs
13:
777:-dimensional convex polytope is a
14:
1074:
1034:
1040:
43:
801:Euclidean minimum spanning tree
1:
950:
995:10.1007/978-3-642-39286-3_17
7:
928:
10:
1079:
1021:. In Gorini, C. A. (ed.).
731:planar straight-line graph
856:projective configurations
522:Exponential random (ERGM)
189:Informational (computing)
935:Topological graph theory
917:. The flip graph of the
845:Scheinerman's conjecture
209:Scientific collaboration
16:Subfield of graph theory
858:lead to many important
817:Hadwiger–Nelson problem
638:Category:Network theory
158:Preferential attachment
1063:Geometric graph theory
1047:Geometric graph theory
919:regular triangulations
891:hyperplane arrangement
841:Circle packing theorem
756:Delaunay triangulation
682:Geometric graph theory
527:Random geometric (RGG)
805:minimum spanning tree
643:Category:Graph theory
1049:at Wikimedia Commons
813:unit distance graph
447:Degree distribution
98:Community structure
923:secondary polytope
828:intersection graph
786:Steinitz's theorem
710:topological graphs
631:Network scientists
557:Soft configuration
1045:Media related to
915:Stasheff polytope
823:of these graphs.
790:polyhedral graphs
688:, concerned with
679:
678:
599:
598:
507:Bianconi–Barabási
401:
400:
219:Artificial neural
194:Telecommunication
1070:
1044:
1030:
1006:
987:Erdös centennial
981:
969:
963:
887:Hamming distance
871:visibility graph
860:symmetric graphs
831:dimension is an
821:chromatic number
782:-connected graph
746:states that any
718:spatial networks
671:
664:
657:
542:Stochastic block
532:Hyperbolic (HGN)
481:
480:
344:
333:
265:
264:
173:Social influence
47:
19:
18:
1078:
1077:
1073:
1072:
1071:
1069:
1068:
1067:
1053:
1052:
1037:
1011:Pisanski, TomaĹľ
961:
953:
945:Spatial network
931:
837:unit disk graph
807:of a Euclidean
797:Euclidean graph
736:Euclidean plane
726:
702:Euclidean plane
675:
613:
578:Boolean network
552:Maximum entropy
502:Barabási–Albert
419:
336:
325:
113:Controllability
78:Complex network
65:
52:
51:
50:
49:
48:
32:Network science
17:
12:
11:
5:
1076:
1066:
1065:
1051:
1050:
1036:
1035:External links
1033:
1032:
1031:
1029:on 2007-09-27.
1007:
982:
976:, ed. (2004).
970:
952:
949:
948:
947:
942:
940:Chemical graph
937:
930:
927:
833:interval graph
809:complete graph
784:. Conversely,
744:Fáry's theorem
725:
722:
677:
676:
674:
673:
666:
659:
651:
648:
647:
646:
645:
640:
634:
633:
628:
623:
615:
614:
612:
611:
608:
604:
601:
600:
597:
596:
595:
594:
585:
580:
572:
571:
567:
566:
565:
564:
559:
554:
549:
544:
539:
534:
529:
524:
519:
517:Watts–Strogatz
514:
509:
504:
499:
494:
486:
485:
477:
476:
472:
471:
470:
469:
464:
459:
454:
449:
444:
439:
434:
429:
421:
420:
418:
417:
412:
406:
403:
402:
399:
398:
397:
396:
391:
386:
381:
376:
371:
366:
361:
353:
352:
348:
347:
346:
345:
338:Incidence list
334:
327:Adjacency list
323:
318:
313:
308:
303:
298:
296:Data structure
293:
288:
283:
278:
270:
269:
261:
260:
254:
253:
252:
251:
246:
241:
236:
231:
226:
224:Interdependent
221:
216:
211:
206:
201:
196:
191:
183:
182:
178:
177:
176:
175:
170:
168:Network effect
165:
163:Balance theory
160:
155:
150:
145:
140:
135:
130:
125:
123:Social capital
120:
115:
110:
105:
100:
95:
90:
85:
80:
75:
67:
66:
64:
63:
57:
54:
53:
42:
41:
40:
39:
38:
35:
34:
28:
27:
15:
9:
6:
4:
3:
2:
1075:
1064:
1061:
1060:
1058:
1048:
1043:
1039:
1038:
1028:
1024:
1020:
1016:
1015:Randić, Milan
1012:
1008:
1004:
1000:
996:
992:
988:
983:
979:
975:
971:
967:
960:
955:
954:
946:
943:
941:
938:
936:
933:
932:
926:
924:
920:
916:
912:
911:associahedron
907:
902:
900:
899:median graphs
896:
895:permutohedron
892:
888:
884:
880:
875:
872:
867:
865:
861:
857:
853:
848:
846:
842:
838:
834:
829:
824:
822:
819:concerns the
818:
814:
810:
806:
802:
798:
793:
791:
787:
783:
781:
776:
772:
768:
764:
759:
757:
753:
752:triangulation
749:
745:
741:
740:line segments
737:
733:
732:
721:
719:
715:
711:
707:
703:
699:
698:combinatorial
695:
691:
687:
683:
672:
667:
665:
660:
658:
653:
652:
650:
649:
644:
641:
639:
636:
635:
632:
629:
627:
624:
622:
619:
618:
617:
616:
609:
606:
605:
603:
602:
593:
589:
586:
584:
581:
579:
576:
575:
574:
573:
569:
568:
563:
562:LFR Benchmark
560:
558:
555:
553:
550:
548:
547:Blockmodeling
545:
543:
540:
538:
535:
533:
530:
528:
525:
523:
520:
518:
515:
513:
512:Fitness model
510:
508:
505:
503:
500:
498:
495:
493:
490:
489:
488:
487:
483:
482:
479:
478:
474:
473:
468:
465:
463:
460:
458:
455:
453:
452:Assortativity
450:
448:
445:
443:
440:
438:
435:
433:
430:
428:
425:
424:
423:
422:
416:
413:
411:
408:
407:
405:
404:
395:
392:
390:
387:
385:
382:
380:
377:
375:
372:
370:
367:
365:
362:
360:
357:
356:
355:
354:
350:
349:
343:
339:
335:
332:
328:
324:
322:
319:
317:
314:
312:
309:
307:
304:
302:
299:
297:
294:
292:
289:
287:
284:
282:
279:
277:
274:
273:
272:
271:
267:
266:
263:
262:
259:
256:
255:
250:
247:
245:
242:
240:
237:
235:
232:
230:
227:
225:
222:
220:
217:
215:
212:
210:
207:
205:
202:
200:
197:
195:
192:
190:
187:
186:
185:
184:
181:Network types
180:
179:
174:
171:
169:
166:
164:
161:
159:
156:
154:
151:
149:
146:
144:
141:
139:
136:
134:
131:
129:
128:Link analysis
126:
124:
121:
119:
118:Graph drawing
116:
114:
111:
109:
106:
104:
101:
99:
96:
94:
91:
89:
86:
84:
81:
79:
76:
74:
71:
70:
69:
68:
62:
59:
58:
56:
55:
46:
37:
36:
33:
30:
29:
25:
21:
20:
1027:the original
1022:
986:
977:
965:
922:
903:
879:partial cube
876:
868:
849:
825:
796:
794:
779:
774:
760:
748:planar graph
729:
727:
686:graph theory
681:
680:
537:Hierarchical
492:Random graph
340: /
329: /
311:Neighborhood
153:Transitivity
133:Optimization
974:Pach, János
692:defined by
583:agent based
497:Erdős–Rényi
138:Reciprocity
103:Percolation
88:Small-world
951:References
906:flip graph
852:Levi graph
767:polyhedron
610:Categories
467:Efficiency
462:Modularity
442:Clustering
427:Centrality
415:Algorithms
239:Dependency
214:Biological
93:Scale-free
883:hypercube
694:geometric
359:Bipartite
281:Component
199:Transport
148:Homophily
108:Evolution
83:Contagion
1057:Category
1017:(2000).
929:See also
771:polytope
763:skeleton
714:vertices
626:Software
588:Epidemic
570:Dynamics
484:Topology
457:Distance
394:Weighted
369:Directed
364:Complete
268:Features
229:Semantic
24:a series
22:Part of
1003:3203608
803:is the
410:Metrics
379:Labeled
249:on-Chip
234:Spatial
143:Closure
1001:
839:. The
761:The 1-
708:, and
690:graphs
621:Topics
475:Models
432:Degree
389:Random
342:matrix
331:matrix
321:Vertex
276:Clique
258:Graphs
204:Social
61:Theory
962:(PDF)
864:cages
765:of a
706:edges
607:Lists
437:Motif
384:Multi
374:Hyper
351:Types
291:Cycle
73:Graph
869:The
862:and
316:Path
306:Loop
301:Edge
244:Flow
991:doi
913:or
826:An
769:or
592:SIR
286:Cut
1059::
1013:;
999:MR
997:.
964:.
925:.
904:A
877:A
866:.
850:A
795:A
792:.
742:.
728:A
720:.
26:on
1005:.
993::
780:k
775:k
670:e
663:t
656:v
590:/
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
