17:
119:(or 1-outerplanar graph) has all of its vertices on the unbounded (outside) face of the graph. A 2-outerplanar graph is a planar graph with the property that, when the vertices on the unbounded face are removed, the remaining vertices all lie on the newly formed unbounded face. And so on.
24:. There are four vertices on the outside face, eight vertices on the second layer (light yellow), and two vertices on the third layer (darker yellow). Because of the symmetries of the graph, no other embedding has fewer layers.
596:
690:
241:
811:
791:
771:
710:
670:
569:
457:
417:
397:
369:
338:
311:
285:
265:
208:
180:
160:
140:
105:
85:
61:
182:
vertices of the embedding, starting with the unbounded face and ending with the vertex, in which each consecutive face and vertex are incident to each other.
347:, according to which every graph property recognizable on graphs of bounded treewidth by finite state tree automata is definable in the monadic second-order
461:
600:
313:-outerplanar graphs and uses their low treewidth in order to quickly approximate several hard graph optimization problems.
142:-outerplanar if it has a planar embedding such that, for every vertex, there is an alternating sequence of at most
340:-outerplanar graphs are one of the most general classes of graphs for which the conjecture has been proved.
815:
Algorithms: ESA 2007, 15th Annual
European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings
841:
574:
344:
244:
740:
675:
621:
492:
290:
21:
217:
8:
651:
796:
776:
756:
695:
655:
643:
625:
554:
529:
510:
442:
436:
402:
382:
354:
323:
296:
270:
250:
193:
165:
145:
125:
90:
70:
46:
474:
548:
116:
629:
16:
818:
726:
609:
533:
519:
478:
470:
822:
817:, Lecture Notes in Computer Science, vol. 4698, Springer, pp. 359–370,
736:
647:
617:
488:
348:
317:
731:
613:
508:(1994), "Approximation algorithms for NP-complete problems on planar graphs",
835:
505:
419:-outerplanar (its outerplanarity index) can be computed in quadratic time.
40:
29:
524:
483:
211:
813:-outerplanar", in Arge, Lars; Hoffmann, Michael; Welzl, Emo (eds.),
43:
that has a planar embedding in which the vertices belong to at most
547:
Chekuri, Chandra; Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri;
641:
546:
243:. However, some bounded-treewidth planar graphs such as the
320:
on metric embedding of minor-closed graph families, the
799:
779:
759:
698:
678:
658:
577:
557:
445:
405:
385:
357:
326:
299:
273:
253:
220:
196:
168:
148:
128:
93:
73:
49:
805:
785:
765:
704:
684:
664:
590:
563:
451:
411:
391:
363:
332:
305:
279:
259:
235:
202:
174:
154:
134:
99:
79:
55:
833:
753:Kammer, Frank (2007), "Determining the smallest
293:covers a planar graph with a constant number of
459:-arboretum of graphs with bounded treewidth",
185:
435:
67:of a planar graph is the minimum value of
730:
652:"Definability equals recognizability for
523:
482:
15:
834:
752:
20:A 3-outerplanar graph, the graph of a
504:
601:SIAM Journal on Discrete Mathematics
287:, linear in the number of vertices.
13:
14:
853:
719:European Journal of Combinatorics
267:-outerplanar only for very large
746:
635:
540:
498:
429:
374:
1:
475:10.1016/S0304-3975(97)00228-4
422:
110:
823:10.1007/978-3-540-75520-3_33
462:Theoretical Computer Science
7:
399:for which a given graph is
186:Properties and applications
10:
858:
650:; Telle, Jan Arne (2017),
351:, has been proven for the
343:A conjectured converse of
122:More formally, a graph is
732:10.1016/j.ejc.2017.06.025
614:10.1137/S0895480102417379
591:{\displaystyle \ell _{1}}
571:-outerplanar graphs into
210:-outerplanar graphs have
672:-outerplanar graphs and
316:In connection with the
63:concentric layers. The
807:
787:
767:
706:
686:
666:
592:
565:
453:
413:
393:
379:The smallest value of
365:
334:
307:
281:
261:
245:nested triangles graph
237:
204:
176:
156:
136:
101:
81:
57:
25:
808:
788:
768:
707:
687:
685:{\displaystyle \ell }
667:
593:
566:
525:10.1145/174644.174650
454:
414:
394:
371:-outerplanar graphs.
366:
335:
308:
282:
262:
238:
205:
177:
157:
137:
102:
82:
58:
19:
797:
777:
757:
696:
676:
656:
575:
555:
443:
403:
383:
355:
324:
297:
271:
251:
236:{\displaystyle 3k-1}
218:
194:
166:
146:
126:
91:
71:
65:outerplanarity index
47:
22:rhombic dodecahedron
644:Bodlaender, Hans L.
551:(2006), "Embedding
439:(1998), "A partial
437:Bodlaender, Hans L.
345:Courcelle's theorem
803:
783:
763:
702:
682:
662:
588:
561:
549:Sinclair, Alistair
511:Journal of the ACM
449:
409:
389:
361:
330:
303:
277:
257:
233:
200:
172:
152:
132:
97:
77:
53:
37:-outerplanar graph
26:
806:{\displaystyle k}
786:{\displaystyle G}
766:{\displaystyle k}
705:{\displaystyle k}
692:-chordal partial
665:{\displaystyle k}
564:{\displaystyle k}
452:{\displaystyle k}
412:{\displaystyle k}
392:{\displaystyle k}
364:{\displaystyle k}
333:{\displaystyle k}
306:{\displaystyle k}
291:Baker's technique
280:{\displaystyle k}
260:{\displaystyle k}
203:{\displaystyle k}
175:{\displaystyle k}
155:{\displaystyle k}
135:{\displaystyle k}
117:outerplanar graph
100:{\displaystyle k}
80:{\displaystyle k}
56:{\displaystyle k}
849:
826:
825:
812:
810:
809:
804:
792:
790:
789:
784:
772:
770:
769:
764:
750:
744:
743:
734:
716:
711:
709:
708:
703:
691:
689:
688:
683:
671:
669:
668:
663:
648:Heggernes, Pinar
639:
633:
632:
597:
595:
594:
589:
587:
586:
570:
568:
567:
562:
544:
538:
536:
527:
502:
496:
495:
486:
458:
456:
455:
450:
433:
418:
416:
415:
410:
398:
396:
395:
390:
370:
368:
367:
362:
339:
337:
336:
331:
312:
310:
309:
304:
286:
284:
283:
278:
266:
264:
263:
258:
242:
240:
239:
234:
209:
207:
206:
201:
181:
179:
178:
173:
161:
159:
158:
153:
141:
139:
138:
133:
106:
104:
103:
98:
87:for which it is
86:
84:
83:
78:
62:
60:
59:
54:
857:
856:
852:
851:
850:
848:
847:
846:
832:
831:
830:
829:
798:
795:
794:
778:
775:
774:
758:
755:
754:
751:
747:
714:
697:
694:
693:
677:
674:
673:
657:
654:
653:
640:
636:
582:
578:
576:
573:
572:
556:
553:
552:
545:
541:
503:
499:
444:
441:
440:
434:
430:
425:
404:
401:
400:
384:
381:
380:
377:
356:
353:
352:
349:logic of graphs
325:
322:
321:
318:GNRS conjecture
298:
295:
294:
272:
269:
268:
252:
249:
248:
219:
216:
215:
195:
192:
191:
188:
167:
164:
163:
147:
144:
143:
127:
124:
123:
113:
92:
89:
88:
72:
69:
68:
48:
45:
44:
12:
11:
5:
855:
845:
844:
828:
827:
802:
782:
762:
745:
701:
681:
661:
642:Jaffke, Lars;
634:
608:(1): 119–136,
585:
581:
560:
539:
518:(1): 153–180,
497:
448:
427:
426:
424:
421:
408:
388:
376:
373:
360:
329:
302:
276:
256:
232:
229:
226:
223:
199:
187:
184:
171:
151:
131:
112:
109:
107:-outerplanar.
96:
76:
52:
9:
6:
4:
3:
2:
854:
843:
842:Planar graphs
840:
839:
837:
824:
820:
816:
800:
780:
760:
749:
742:
738:
733:
728:
724:
720:
713:
699:
679:
659:
649:
645:
638:
631:
627:
623:
619:
615:
611:
607:
603:
602:
583:
579:
558:
550:
543:
535:
531:
526:
521:
517:
513:
512:
507:
501:
494:
490:
485:
480:
476:
472:
469:(1–2): 1–45,
468:
464:
463:
446:
438:
432:
428:
420:
406:
386:
372:
358:
350:
346:
341:
327:
319:
314:
300:
292:
288:
274:
254:
246:
230:
227:
224:
221:
213:
197:
183:
169:
149:
129:
120:
118:
108:
94:
74:
66:
50:
42:
38:
36:
31:
23:
18:
814:
748:
722:
718:
637:
605:
599:
542:
515:
509:
500:
466:
460:
431:
378:
342:
315:
289:
189:
121:
114:
64:
41:planar graph
34:
33:
30:graph theory
27:
725:: 191–234,
375:Recognition
773:such that
484:1874/18312
423:References
162:faces and
111:Definition
680:ℓ
580:ℓ
506:Baker, B.
228:−
212:treewidth
836:Category
630:13925350
214:at most
741:3692146
712:-trees"
622:2257250
534:9706753
493:1647486
247:may be
739:
628:
620:
532:
491:
715:(PDF)
626:S2CID
530:S2CID
39:is a
190:The
32:, a
819:doi
793:is
727:doi
610:doi
598:",
520:doi
479:hdl
471:doi
467:209
115:An
28:In
838::
737:MR
735:,
723:66
721:,
717:,
646:;
624:,
618:MR
616:,
606:20
604:,
528:,
516:41
514:,
489:MR
487:,
477:,
465:,
821::
801:k
781:G
761:k
729::
700:k
660:k
612::
584:1
559:k
537:.
522::
481::
473::
447:k
407:k
387:k
359:k
328:k
301:k
275:k
255:k
231:1
225:k
222:3
198:k
170:k
150:k
130:k
95:k
75:k
51:k
35:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
