687:
is an extension of the concept of graph density defined above from finite graphs to infinite graphs. Intuitively, an infinite graph has arbitrarily large finite subgraphs with any density less than its upper density, and does not have arbitrarily large finite subgraphs with density greater than its
39:. The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem.
356:
203:
468:
1114:
541:
1147:
1133:
619:
505:
674:
1340:
1131:
considered that the sparsity/density dichotomy makes it necessary to consider infinite graph classes instead of single graph instances. They defined
940:
edges (except for graphs with fewer than 3 vertices), and that any subgraph of a planar graph is planar, together imply that the planar graphs are
218:
69:
1205:
1469:
Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in
Epstein, Leah; Ferragina, Paolo (eds.),
212:, simple graphs, the maximum possible edges is twice that of undirected graphs (as there are two directions to an edge) so the density is:
1311:
372:
1415:
924:
Other graph families not characterized by their sparsity can also be described in this way. For instance the facts that any
1145:-subdivision in a subgraph of a graph in the class. To the contrary, if such a threshold does not exist, the class is
1056:
1474:
1438:
1365:
1249:
1471:
Algorithms – ESA 2012: 20th Annual
European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings
1382:(2010), "From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits",
1241:
510:
914:
28:
550:
701:
1022:
484:
1395:
1379:
1163:
1158:
The classes of graphs with bounded degeneracy and of nowhere dense graphs are both included in the
1499:
624:
1391:
1375:
1215:; Moré, Jorge J. (1983), "Estimation of sparse Jacobian matrices and graph coloring Problems",
369:
is the number of vertices in the graph. The maximum number of edges for an undirected graph is
1306:
705:
32:
1425:
1332:
1298:
31:
in which the number of edges is close to the maximal number of edges (where every pair of
8:
1159:
871:
1447:
1276:
1411:
1361:
1255:
1245:
1212:
1197:
1179:
949:
1478:
1457:
1403:
1320:
1286:
1224:
544:
1482:
1421:
1328:
1294:
1267:
Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs",
957:
1151:. Properties of the nowhere dense vs somewhere dense dichotomy are discussed in
1433:
1290:
1184:
471:
209:
1461:
1407:
1324:
1493:
1259:
351:{\displaystyle D={\frac {|E|}{2{\binom {|V|}{2}}}}={\frac {|E|}{|V|(|V|-1)}}}
35:
is connected by one edge). The opposite, a graph with only a few edges, is a
1137:
graph classes as those classes of graphs for which there exists a threshold
700:
with density α have a bounded number of vertices. It can be shown using the
925:
902:
198:{\displaystyle D={\frac {|E|}{\binom {|V|}{2}}}={\frac {2|E|}{|V|(|V|-1)}}}
60:
1358:
Data
Structures and Algorithms with Object-Oriented Design Patterns in C++
481:
For families of graphs of increasing size, one often calls them sparse if
910:
20:
1026:
883:
1436:; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms",
1452:
1281:
1402:, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer,
1228:
46:
of simple graphs is defined to be the ratio of the number of edges
1021:-sparse is equivalent to the graphs in the family having bounded
693:
1049:-sparse graphs. Similarly, the graphs of degeneracy at most
463:{\displaystyle {\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}}
1390:
1374:
1152:
1128:
1309:(1964), "Decomposition of finite graphs into forests",
547:, a more restrictive definition of sparse is used like
688:
upper density. Formally, the upper density of a graph
1123:
1059:
627:
553:
513:
487:
375:
221:
72:
979:-sparsity may be performed in polynomial time when
704:that the upper density can only be 1 or one of the
1108:
696:of the values α such that the finite subgraphs of
668:
613:
535:
499:
462:
350:
197:
1386:, European Mathematical Society, pp. 135–165
1095:
1074:
404:
379:
1491:
1109:{\displaystyle \left(d,{\binom {d+1}{2}}\right)}
1477:, vol. 7501, Springer, pp. 802–812,
1468:
1167:
1029:. More precisely, it follows from a result of
795:(see, e.g., Diestel, edition 5, p. 189).
1432:
1305:
1202:Dictionary of Algorithms and Data Structures,
1030:
807:
277:
252:
123:
98:
1400:Sparsity: Graphs, Structures, and Algorithms
1141:such that every complete graph appears as a
56:with respect to the maximum possible edges.
1211:
1009:such that the graphs in the family are all
475:
1312:Journal of the London Mathematical Society
1266:
803:
798:
1451:
1338:
1280:
1117:
16:Graph with almost the max amount of edges
822:-sparse if every nonempty subgraph with
1235:
878:-tight graphs, forests are exactly the
1492:
1355:
1153:Nešetřil & Ossona de Mendez (2012)
1129:Nešetřil & Ossona de Mendez (2010)
1033:that the graphs of arboricity at most
536:{\displaystyle |V|\rightarrow \infty }
1339:Lick, Don R; White, Arthur T (1970).
1001:For a graph family, the existence of
967:Streinu and Theran show that testing
948:-sparse graph is planar. Similarly,
1162:, graph families that exclude some
470:, so the maximal density is 1 (for
13:
1217:SIAM Journal on Numerical Analysis
1124:Sparse and dense classes of graphs
1078:
614:{\displaystyle |E|=O(|V|\log |V|)}
530:
383:
256:
102:
14:
1511:
1475:Lecture Notes in Computer Science
1439:European Journal of Combinatorics
1208:. Retrieved on 29 September 2005.
1384:European Congress of Mathematics
882:-sparse graphs, and graphs with
679:
474:) and the minimal density is 0 (
1345:Canadian Journal of Mathematics
663:
659:
651:
647:
637:
629:
608:
604:
596:
585:
577:
573:
563:
555:
527:
523:
515:
500:{\displaystyle D\rightarrow 0}
491:
451:
441:
433:
429:
425:
417:
394:
386:
342:
332:
324:
320:
316:
308:
301:
293:
267:
259:
240:
232:
189:
179:
171:
167:
163:
155:
148:
140:
113:
105:
91:
83:
1:
1242:Graduate Texts in Mathematics
1190:
1483:10.1007/978-3-642-33090-2_69
944:-sparse. However, not every
7:
1307:Nash-Williams, C. St. J. A.
1173:
808:Streinu & Theran (2009)
365:is the number of edges and
10:
1516:
1291:10.1016/j.disc.2007.07.104
1236:Diestel, Reinhard (2005),
1168:Telle & Villanger 2012
669:{\displaystyle |E|=O(|V|)}
1462:10.1016/j.ejc.2008.12.018
1408:10.1007/978-3-642-27875-4
1396:Ossona de Mendez, Patrice
1380:Ossona de Mendez, Patrice
1360:, John Wiley & Sons,
1164:complete bipartite graph
909:-sparse graphs, and the
860:-sparse and has exactly
810:define a graph as being
804:Lee & Streinu (2008)
63:, the graph density is:
1325:10.1112/jlms/s1-39.1.12
799:Sparse and tight graphs
476:Coleman & Moré 1983
1356:Preiss, first (1998),
1110:
706:superparticular ratios
670:
615:
537:
501:
464:
352:
199:
1341:"k-Degenerate graphs"
1204:Paul E. Black (ed.),
1118:Lick & White 1970
1111:
932:vertices has at most
826:vertices has at most
671:
616:
538:
502:
465:
353:
200:
1269:Discrete Mathematics
1160:biclique-free graphs
1057:
1031:Nash-Williams (1964)
625:
551:
511:
485:
373:
219:
70:
1244:, Springer-Verlag,
956:-sparse and planar
702:Erdős–Stone theorem
1392:Nešetřil, Jaroslav
1376:Nešetřil, Jaroslav
1213:Coleman, Thomas F.
1106:
1025:or having bounded
950:outerplanar graphs
666:
611:
533:
497:
460:
348:
195:
1417:978-3-642-27874-7
1180:Bounded expansion
1093:
987:are integers and
458:
402:
346:
284:
275:
193:
128:
121:
1507:
1485:
1464:
1455:
1446:(8): 1944–1964,
1428:
1387:
1370:
1352:
1335:
1301:
1284:
1275:(8): 1425–1437,
1262:
1231:
1116:-sparse graphs (
1115:
1113:
1112:
1107:
1105:
1101:
1100:
1099:
1098:
1089:
1077:
1052:
1048:
1037:are exactly the
1036:
1020:
1008:
1004:
997:
986:
982:
978:
963:
958:bipartite graphs
955:
947:
943:
939:
931:
920:
917:are exactly the
908:
905:are exactly the
901:-sparse graphs.
900:
889:are exactly the
888:
881:
877:
874:are exactly the
869:
859:
848:-tight if it is
847:
835:
825:
821:
794:
793:
791:
790:
784:
781:
772:
770:
769:
766:
763:
756:
754:
753:
750:
747:
740:
738:
737:
734:
731:
724:
722:
721:
718:
715:
699:
691:
675:
673:
672:
667:
662:
654:
640:
632:
620:
618:
617:
612:
607:
599:
588:
580:
566:
558:
545:computer science
543:. Sometimes, in
542:
540:
539:
534:
526:
518:
506:
504:
503:
498:
469:
467:
466:
461:
459:
454:
444:
436:
428:
420:
414:
409:
408:
407:
398:
397:
389:
382:
368:
364:
357:
355:
354:
349:
347:
345:
335:
327:
319:
311:
305:
304:
296:
290:
285:
283:
282:
281:
280:
271:
270:
262:
255:
244:
243:
235:
229:
204:
202:
201:
196:
194:
192:
182:
174:
166:
158:
152:
151:
143:
134:
129:
127:
126:
117:
116:
108:
101:
95:
94:
86:
80:
55:
53:
1515:
1514:
1510:
1509:
1508:
1506:
1505:
1504:
1490:
1489:
1418:
1368:
1351:(5): 1082–1096.
1252:
1229:10.1137/0720013
1196:Paul E. Black,
1193:
1176:
1166:as a subgraph (
1134:somewhere dense
1126:
1094:
1079:
1073:
1072:
1071:
1064:
1060:
1058:
1055:
1054:
1050:
1038:
1034:
1010:
1006:
1002:
988:
984:
980:
968:
961:
953:
945:
941:
933:
929:
921:-tight graphs.
918:
915:rigidity theory
906:
890:
886:
879:
875:
861:
849:
837:
827:
823:
811:
801:
785:
782:
777:
776:
774:
767:
764:
761:
760:
758:
751:
748:
745:
744:
742:
735:
732:
729:
728:
726:
719:
716:
713:
712:
710:
708:
697:
689:
682:
658:
650:
636:
628:
626:
623:
622:
603:
595:
584:
576:
562:
554:
552:
549:
548:
522:
514:
512:
509:
508:
486:
483:
482:
472:complete graphs
440:
432:
424:
416:
415:
413:
403:
393:
385:
384:
378:
377:
376:
374:
371:
370:
366:
362:
331:
323:
315:
307:
306:
300:
292:
291:
289:
276:
266:
258:
257:
251:
250:
249:
245:
239:
231:
230:
228:
220:
217:
216:
178:
170:
162:
154:
153:
147:
139:
135:
133:
122:
112:
104:
103:
97:
96:
90:
82:
81:
79:
71:
68:
67:
59:For undirected
49:
47:
17:
12:
11:
5:
1513:
1503:
1502:
1500:Graph families
1488:
1487:
1466:
1430:
1416:
1388:
1372:
1366:
1353:
1336:
1303:
1264:
1250:
1233:
1223:(1): 187–209,
1209:
1192:
1189:
1188:
1187:
1185:Dense subgraph
1182:
1175:
1172:
1125:
1122:
1104:
1097:
1092:
1088:
1085:
1082:
1076:
1070:
1067:
1063:
800:
797:
681:
678:
665:
661:
657:
653:
649:
646:
643:
639:
635:
631:
610:
606:
602:
598:
594:
591:
587:
583:
579:
575:
572:
569:
565:
561:
557:
532:
529:
525:
521:
517:
496:
493:
490:
457:
453:
450:
447:
443:
439:
435:
431:
427:
423:
419:
412:
406:
401:
396:
392:
388:
381:
359:
358:
344:
341:
338:
334:
330:
326:
322:
318:
314:
310:
303:
299:
295:
288:
279:
274:
269:
265:
261:
254:
248:
242:
238:
234:
227:
224:
206:
205:
191:
188:
185:
181:
177:
173:
169:
165:
161:
157:
150:
146:
142:
138:
132:
125:
120:
115:
111:
107:
100:
93:
89:
85:
78:
75:
15:
9:
6:
4:
3:
2:
1512:
1501:
1498:
1497:
1495:
1484:
1480:
1476:
1472:
1467:
1463:
1459:
1454:
1449:
1445:
1441:
1440:
1435:
1431:
1427:
1423:
1419:
1413:
1409:
1405:
1401:
1397:
1393:
1389:
1385:
1381:
1377:
1373:
1369:
1367:0-471-24134-2
1363:
1359:
1354:
1350:
1346:
1342:
1337:
1334:
1330:
1326:
1322:
1318:
1314:
1313:
1308:
1304:
1300:
1296:
1292:
1288:
1283:
1278:
1274:
1270:
1265:
1261:
1257:
1253:
1251:3-540-26183-4
1247:
1243:
1239:
1234:
1230:
1226:
1222:
1218:
1214:
1210:
1207:
1203:
1199:
1195:
1194:
1186:
1183:
1181:
1178:
1177:
1171:
1169:
1165:
1161:
1156:
1154:
1150:
1149:
1148:nowhere dense
1144:
1140:
1136:
1135:
1130:
1121:
1119:
1102:
1090:
1086:
1083:
1080:
1068:
1065:
1061:
1046:
1042:
1032:
1028:
1024:
1018:
1014:
999:
996:
992:
976:
972:
965:
959:
951:
937:
927:
922:
916:
912:
904:
903:Pseudoforests
898:
894:
885:
873:
868:
864:
857:
853:
845:
841:
834:
830:
819:
815:
809:
805:
796:
788:
780:
707:
703:
695:
686:
685:Upper density
680:Upper density
677:
655:
644:
641:
633:
600:
592:
589:
581:
570:
567:
559:
546:
519:
494:
488:
479:
477:
473:
455:
448:
445:
437:
421:
410:
399:
390:
339:
336:
328:
312:
297:
286:
272:
263:
246:
236:
225:
222:
215:
214:
213:
211:
186:
183:
175:
159:
144:
136:
130:
118:
109:
87:
76:
73:
66:
65:
64:
62:
61:simple graphs
57:
52:
45:
44:graph density
40:
38:
34:
30:
26:
22:
1470:
1453:math/0703921
1443:
1437:
1399:
1383:
1357:
1348:
1344:
1316:
1310:
1282:math/0702129
1272:
1268:
1238:Graph Theory
1237:
1220:
1216:
1201:
1198:Sparse graph
1157:
1146:
1142:
1138:
1132:
1127:
1044:
1040:
1016:
1012:
1000:
994:
990:
974:
970:
966:
935:
926:planar graph
923:
911:Laman graphs
896:
892:
870:edges. Thus
866:
862:
855:
851:
843:
839:
832:
828:
817:
813:
802:
786:
778:
684:
683:
480:
360:
207:
58:
50:
43:
41:
37:sparse graph
36:
24:
18:
1434:Streinu, I.
913:arising in
836:edges, and
25:dense graph
21:mathematics
1191:References
1027:arboricity
1023:degeneracy
884:arboricity
1319:(1): 12,
1260:181535575
964:-sparse.
593:
531:∞
528:→
492:→
446:−
337:−
184:−
1494:Category
1398:(2012),
1174:See also
621:or even
210:directed
33:vertices
1426:2920058
1333:0161333
1299:2392060
1200:, from
792:
775:
771:
759:
755:
743:
739:
727:
723:
711:
694:infimum
692:is the
1424:
1414:
1364:
1331:
1297:
1258:
1248:
993:< 2
361:where
54:|
48:|
1448:arXiv
1277:arXiv
983:and
962:(2,4)
954:(2,3)
946:(3,6)
942:(3,6)
928:with
919:(2,3)
907:(1,0)
880:(1,1)
876:(1,1)
872:trees
29:graph
27:is a
1412:ISBN
1362:ISBN
1256:OCLC
1246:ISBN
1206:NIST
1053:are
1005:and
989:0 ≤
960:are
952:are
806:and
773:, …
208:For
42:The
23:, a
1479:doi
1458:doi
1404:doi
1321:doi
1287:doi
1273:308
1225:doi
1170:).
1120:).
938:– 6
789:+ 1
709:0,
590:log
507:as
478:).
19:In
1496::
1473:,
1456:,
1444:30
1442:,
1422:MR
1420:,
1410:,
1394:;
1378:;
1349:22
1347:.
1343:.
1329:MR
1327:,
1317:39
1315:,
1295:MR
1293:,
1285:,
1271:,
1254:,
1240:,
1221:20
1219:,
1155:.
998:.
865:−
863:kn
854:,
842:,
831:−
829:kn
816:,
757:,
741:,
725:,
676:.
1486:.
1481::
1465:.
1460::
1450::
1429:.
1406::
1371:.
1323::
1302:.
1289::
1279::
1263:.
1232:.
1227::
1143:t
1139:t
1103:)
1096:)
1091:2
1087:1
1084:+
1081:d
1075:(
1069:,
1066:d
1062:(
1051:d
1047:)
1045:a
1043:,
1041:a
1039:(
1035:a
1019:)
1017:l
1015:,
1013:k
1011:(
1007:l
1003:k
995:k
991:l
985:l
981:k
977:)
975:l
973:,
971:k
969:(
936:n
934:3
930:n
899:)
897:k
895:,
893:k
891:(
887:k
867:l
858:)
856:l
852:k
850:(
846:)
844:l
840:k
838:(
833:l
824:n
820:)
818:l
814:k
812:(
787:n
783:/
779:n
768:5
765:/
762:4
752:4
749:/
746:3
736:3
733:/
730:2
720:2
717:/
714:1
698:G
690:G
664:)
660:|
656:V
652:|
648:(
645:O
642:=
638:|
634:E
630:|
609:)
605:|
601:V
597:|
586:|
582:V
578:|
574:(
571:O
568:=
564:|
560:E
556:|
524:|
520:V
516:|
495:0
489:D
456:2
452:)
449:1
442:|
438:V
434:|
430:(
426:|
422:V
418:|
411:=
405:)
400:2
395:|
391:V
387:|
380:(
367:V
363:E
343:)
340:1
333:|
329:V
325:|
321:(
317:|
313:V
309:|
302:|
298:E
294:|
287:=
278:)
273:2
268:|
264:V
260:|
253:(
247:2
241:|
237:E
233:|
226:=
223:D
190:)
187:1
180:|
176:V
172:|
168:(
164:|
160:V
156:|
149:|
145:E
141:|
137:2
131:=
124:)
119:2
114:|
110:V
106:|
99:(
92:|
88:E
84:|
77:=
74:D
51:E
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.