218:
the subgraph forces a linear number of crossings to be created. As a compromise between finding the optimal planarization of a planar subgraph plus one edge, and keeping a fixed embedding, it is possible to search over all embeddings of the planarized subgraph and find the one that minimizes the number of crossings formed by the new edge.
196:
Once a large planar subgraph has been found, the incremental planarization process continues by considering the remaining edges one by one. As it does so, it maintains a planarization of the subgraph formed by the edges that have already been considered. It adds each new edge to a planar embedding of
217:
Fixing the embedding of the planarized subgraph is not necessarily optimal in terms of the number of crossings that result. In fact, there exist graphs that are formed by adding one edge to a planar subgraph, where the optimal drawing has only two crossings but where fixing the planar embedding of
80:
is found within the given graph. Then, the remaining edges that are not already part of this subgraph are added back one at a time, and routed through an embedding of the planar subgraph. When one of these edges crosses an already-embedded edge, the two edges that cross are replaced by two-edge
197:
this subgraph, forming a drawing with crossings, and then replaces each crossing point with a new artificial vertex subdividing the two edges that cross. In some versions of this procedure, the order for adding edges is arbitrary, but it is also possible to choose the ordering to be a
204:
In the simplest form of this process, the planar embedding of the planarized subgraph is not allowed to change while new edges are added. In order to add each new edge in a way that minimizes the number of crossings it forms, one can use a
93:
Using incremental planarization for graph drawing is most effective when the first step of the process finds as large a planar graph as possible. Unfortunately, finding the planar subgraph with the maximum possible number of edges (the
213:
of the current embedding, in order to find the shortest sequence of faces of the embedding and edges to be crossed that connects the endpoints of the new edge to each other. This process takes polynomial time per edge.
320:
141:
as a subgraph of the given graph. Alternatively, if it is expected that the planar subgraph will include almost all of the edges of the given graph, leaving only a small number
57:
Planarization may be performed by using any method to find a drawing (with crossings) for the given graph, and then replacing each crossing point by a new artificial
85:
stage is added to the planarization process, in which edges with many crossings are removed and re-added in an attempt to improve the planarization.
354:
Călinescu, Gruia; Fernandes, Cristina G.; Finkler, Ulrich; Karloff, Howard (1998), "A better approximation algorithm for finding planar subgraphs",
333:
172:
of a given graph. Again, this is NP-hard, but fixed-parameter tractable when all but a few vertices belong to the induced subgraph.
137:
of one-third, simply by finding a spanning tree. A better approximation ratio, 9/4, is known, based on a method for finding a large
574:
81:
paths, with a new artificial vertex that represents the crossing point placed at the middle of both paths. In some case a third
415:
329:
145:
of non-planar edges for the incremental planarization process, then one can solve the problem exactly by using a
300:
17:
77:
576:
Graph
Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers
82:
411:
157:
algorithm, with no guarantees on running time, but with good performance in practice. This parameter
368:
146:
149:
algorithm whose running time is linear in the graph size but non-polynomial in the parameter
133: − 1 edges. Thus, it is easy to approximate the maximum planar subgraph within an
206:
188:; their proof leads to a polynomial time algorithm for finding an induced subgraph of this size.
573:
Edwards, Keith; Farr, Graham (2002), "An algorithm for finding large induced planar subgraphs",
661:
526:
407:
363:
201:, running the same algorithm several times and returning the best planarization that it finds.
185:
58:
633:
594:
551:
487:
433:
385:
8:
134:
66:
62:
264:, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, Florida
180:/(Δ + 1) on the size of the largest planar induced subgraph, as a function of
637:
555:
437:
389:
198:
530:
417:
Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of
Computing (STOC '07)
502:
460:
296:
559:
441:
110:
algorithm that solves the problem exactly or that approximates it arbitrarily well.
641:
621:
580:
539:
505:
475:
421:
393:
373:
288:
257:
169:
103:
629:
590:
547:
483:
429:
381:
118:
107:
168:
There has also been some study of a related problem, finding the largest planar
154:
138:
625:
655:
126:
43:
585:
425:
76:, the planarization process is split into two stages. First, a large planar
609:
456:
377:
253:
252:
Buchheim, Christoph; Chimani, Markus; Gutwenger, Carsten; Jünger, Michael;
47:
35:
31:
479:
579:, Lecture Notes in Comp. Sci., vol. 2265, Springer, pp. 75–80,
543:
284:
532:
50th Annual IEEE Symposium on
Foundations of Computer Science (FOCS '09)
210:
461:"Maximum planar subgraphs and nice embeddings: practical layout tools"
612:; Weiskircher, René (2005), "Inserting an edge into a planar graph",
510:
51:
99:
529:(2009), "Planarity allowing few error vertices in linear time",
353:
282:
251:
607:
293:
Graph
Drawing: Algorithms for the Visualization of Graphs
184:, the number of vertices in the given graph, and Δ, its
500:
88:
414:(2007), "Computing crossing number in linear time",
61:, causing each crossed edge to be subdivided into a
54:
the non-planar graphs within a larger planar graph.
191:
406:
295:(1st ed.), Prentice Hall, pp. 215–218,
653:
106:, implying that there probably does not exist a
65:. The original graph will be represented as an
153:. The problem may also be solved exactly by a
525:
454:
572:
262:Handbook of Graph Drawing and Visualization
173:
121:, the largest planar subgraph has at most 3
256:(2014), "Crossings and planarization", in
584:
367:
314:
312:
318:
27:Technique for drawing non-planar graphs
14:
654:
349:
347:
309:
501:
278:
276:
274:
272:
247:
245:
243:
241:
239:
237:
235:
233:
231:
125: − 6 edges, and any
344:
89:Finding the largest planar subgraph
24:
269:
228:
50:to graphs that are not planar, by
25:
673:
330:Technical University of Dortmund
601:
332:, Section 4.3.1, archived from
192:Adding edges to a planarization
566:
519:
494:
448:
400:
13:
1:
291:; Tollis, Ioannis G. (1998),
221:
129:forms a planar subgraph with
7:
10:
678:
322:Computing Crossing Numbers
626:10.1007/s00453-004-1128-8
176:proved a tight bound of 3
174:Edwards & Farr (2002)
147:fixed-parameter tractable
74:incremental planarization
42:is a method of extending
319:Chimani, Markus (2008),
586:10.1007/3-540-45848-4_6
527:Kawarabayashi, Ken-ichi
426:10.1145/1250790.1250848
408:Kawarabayashi, Ken-ichi
283:Di Battista, Giuseppe;
207:shortest path algorithm
96:maximum planar subgraph
378:10.1006/jagm.1997.0920
328:, Ph.D. dissertation,
69:of its planarization.
480:10.1007/s004539900036
356:Journal of Algorithms
608:Gutwenger, Carsten;
544:10.1109/FOCS.2009.45
538:, pp. 639–648,
420:, pp. 382–390,
135:approximation ratio
503:Weisstein, Eric W.
199:random permutation
83:local optimization
289:Tamassia, Roberto
258:Tamassia, Roberto
16:(Redirected from
669:
646:
644:
605:
599:
597:
588:
570:
564:
562:
537:
523:
517:
516:
515:
506:"Graph Skewness"
498:
492:
490:
465:
452:
446:
444:
404:
398:
396:
371:
351:
342:
340:
338:
327:
316:
307:
305:
280:
267:
265:
249:
170:induced subgraph
161:is known as the
21:
677:
676:
672:
671:
670:
668:
667:
666:
652:
651:
650:
649:
606:
602:
571:
567:
535:
524:
520:
499:
495:
463:
453:
449:
405:
401:
352:
345:
336:
325:
317:
310:
303:
281:
270:
250:
229:
224:
194:
119:connected graph
108:polynomial time
91:
67:immersion minor
28:
23:
22:
15:
12:
11:
5:
675:
665:
664:
648:
647:
620:(4): 289–308,
600:
565:
518:
493:
447:
399:
369:10.1.1.37.4317
362:(2): 269–302,
343:
308:
301:
268:
226:
225:
223:
220:
193:
190:
186:maximum degree
165:of the graph.
155:branch and cut
139:partial 2-tree
90:
87:
26:
18:Graph skewness
9:
6:
4:
3:
2:
674:
663:
662:Planar graphs
660:
659:
657:
643:
639:
635:
631:
627:
623:
619:
615:
611:
610:Mutzel, Petra
604:
596:
592:
587:
582:
578:
577:
569:
561:
557:
553:
549:
545:
541:
534:
533:
528:
522:
513:
512:
507:
504:
497:
489:
485:
481:
477:
473:
469:
462:
458:
451:
443:
439:
435:
431:
427:
423:
419:
418:
413:
409:
403:
395:
391:
387:
383:
379:
375:
370:
365:
361:
357:
350:
348:
339:on 2015-11-16
335:
331:
324:
323:
315:
313:
304:
298:
294:
290:
286:
279:
277:
275:
273:
263:
259:
255:
254:Mutzel, Petra
248:
246:
244:
242:
240:
238:
236:
234:
232:
227:
219:
215:
212:
208:
202:
200:
189:
187:
183:
179:
175:
171:
166:
164:
160:
156:
152:
148:
144:
140:
136:
132:
128:
127:spanning tree
124:
120:
116:
111:
109:
105:
101:
97:
86:
84:
79:
75:
70:
68:
64:
60:
55:
53:
49:
48:planar graphs
46:methods from
45:
44:graph drawing
41:
40:planarization
37:
33:
19:
617:
614:Algorithmica
613:
603:
575:
568:
531:
521:
509:
496:
474:(1): 33–59,
471:
468:Algorithmica
467:
455:Jünger, M.;
450:
416:
402:
359:
355:
334:the original
321:
292:
285:Eades, Peter
261:
216:
203:
195:
181:
177:
167:
162:
158:
150:
142:
130:
122:
114:
112:
98:problem) is
95:
92:
73:
71:
56:
39:
36:graph theory
32:mathematical
29:
412:Reed, Bruce
104:MaxSNP-hard
457:Mutzel, P.
302:0133016153
222:References
211:dual graph
511:MathWorld
364:CiteSeerX
52:embedding
34:field of
656:Category
560:11647021
459:(1996),
442:13000831
163:skewness
117:-vertex
78:subgraph
642:6441726
634:2122529
595:1962420
552:2648441
488:1394493
434:2402463
394:8329680
386:1622397
260:(ed.),
209:in the
100:NP-hard
30:In the
640:
632:
593:
558:
550:
486:
440:
432:
392:
384:
366:
299:
113:In an
102:, and
59:vertex
638:S2CID
556:S2CID
536:(PDF)
464:(PDF)
438:S2CID
390:S2CID
337:(PDF)
326:(PDF)
297:ISBN
63:path
622:doi
581:doi
540:doi
476:doi
422:doi
374:doi
72:In
658::
636:,
630:MR
628:,
618:41
616:,
591:MR
589:,
554:,
548:MR
546:,
508:.
484:MR
482:,
472:16
470:,
466:,
436:,
430:MR
428:,
410:;
388:,
382:MR
380:,
372:,
360:27
358:,
346:^
311:^
287:;
271:^
230:^
38:,
645:.
624::
598:.
583::
563:.
542::
514:.
491:.
478::
445:.
424::
397:.
376::
341:.
306:.
266:.
182:n
178:n
159:k
151:k
143:k
131:n
123:n
115:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.