1‑планарный граф

1‑планарный рису­нок гра­фа Хиву­да — шесть рёбер име­ют еди­нич­ные пере­се­че­ния, а осталь­ные 15 рёбер не пере­се­ка­ют­ся.

В топо­ло­ги­че­ской тео­рии гра­фов 1‑планарный граф — граф, кото­рый может быть нари­со­ван в евкли­до­вой плос­ко­сти таким обра­зом, что каж­дое реб­ро име­ет мак­си­мум одно пере­се­че­ние с един­ствен­ным дру­гим реб­ром.

Раскраска

1‑планарные гра­фы пер­вым рас­смат­ри­вал Рин­гель, кото­рый пока­зал, что они могут быть рас­кра­ше­ны, не пре­вы­шая семи цве­тов[1]. Позд­нее точ­ное чис­ло цве­тов, необ­хо­ди­мых для рас­крас­ки этих гра­фов, (в худ­шем слу­чае) было умень­ше­но до шести[2]. При­мер пол­но­го гра­фа K6, явля­ю­ще­го­ся 1‑планарным, пока­зы­ва­ет, что 1‑планарные гра­фы ино­гда могут тре­бо­вать для рас­крас­ки шести цве­тов. Одна­ко дока­за­тель­ство доста­точ­но­сти шести цве­том не явля­ет­ся про­стым.

Рас­крас­ка вер­шин и гра­ней тре­уголь­ной приз­мы тре­бу­ет шесть цве­тов

Пово­дом для рас­смот­ре­ния 1‑планарных гра­фов Рин­ге­лем была попыт­ка решить вари­ант зада­чи тоталь­ной рас­крас­ки для пла­нар­ных гра­фов, в кото­рой рас­кра­ши­ва­ют­ся вер­ши­ны и гра­ни пла­нар­но­го гра­фа таким обра­зом, что ника­кие две смеж­ные вер­ши­ны не име­ют оди­на­ко­вый цвет и любые две смеж­ные гра­ни тоже долж­ны быть рас­кра­ше­ны в раз­ные цве­та, а так­же цве­та вер­шин и смеж­ных им гра­ней долж­ны отли­чать­ся. Оче­вид­но, что это мож­но сде­лать с помо­щью вось­ми кра­сок, если при­ме­нить тео­ре­му о четы­рёх крас­ках для гра­фа и его двой­ствен­но­го гра­фа раз­дель­но, при­ме­нив два непе­ре­се­ка­ю­щих­ся набо­ра четы­рёх кра­сок. Одна­ко мож­но полу­чить мень­шее коли­че­ство кра­сок, если сфор­ми­ро­вать вспо­мо­га­тель­ный граф, име­ю­щий по вер­шине для каж­дой вер­ши­ны и гра­ни исход­но­го пла­нар­но­го гра­фа, и в кото­ром две вер­ши­ны вспо­мо­га­тель­но­го гра­фа смеж­ны, если они соот­вет­ству­ют смеж­ным объ­ек­там задан­но­го пла­нар­но­го гра­фа. Рас­крас­ка вер­шин вспо­мо­га­тель­но­го гра­фа соот­вет­ству­ет рас­крас­ке исход­но­го пла­нар­но­го гра­фа. Вспо­мо­га­тель­ный граф явля­ет­ся 1‑планарным, отку­да сле­ду­ет, что зада­ча Рин­ге­ля рас­крас­ки вер­шин и гра­ней может быть реше­на с исполь­зо­ва­ни­ем шести цве­тов[2]. Граф K6 не может быть полу­чен как вспо­мо­га­тель­ный граф таким обра­зом, но, тем не менее, зада­ча рас­крас­ки вер­шин и гра­ней ино­гда тре­бу­ет шести цве­тов. Напри­мер, если рас­кра­ши­вать пла­нар­ный граф тре­уголь­ной приз­мы, её 6 вер­шин + 5 гра­ней тре­бу­ет шести цве­тов[3].

Плотность рёбер

Любой 1‑планарный граф с n вер­ши­на­ми име­ет не более 4n − 8 рёбер[4]. Более стро­го, каж­дый рису­нок 1‑планарного гра­фа име­ет не более n − 2 пере­се­че­ний. Уда­ле­ние одно­го реб­ра из каж­дой пере­се­ка­ю­щей­ся пары рёбер остав­ля­ет пла­нар­ный граф, кото­рый име­ет не более 3n − 6 рёбер, отку­да немед­лен­но сле­ду­ет гра­ни­ца чис­ла рёбер 4n − 8 исход­но­го 1‑планарного гра­фа[5]. Одна­ко, в отли­чие от пла­нар­ных гра­фов (для кото­рых все мак­си­маль­ные пла­нар­ные гра­фы на задан­ном мно­же­стве вер­шин име­ют оди­на­ко­вое чис­ло рёбер), суще­ству­ют мак­си­маль­ные 1‑планарные гра­фы (гра­фы, в кото­рые нель­зя доба­вить реб­ро с сохра­не­ни­ем 1‑планарности), кото­рые име­ют суще­ствен­но менее 4n − 8 рёбер[6]. Гра­ни­ца 4n − 8 мак­си­маль­но­го воз­мож­но­го чис­ла рёбер в 1‑планарном гра­фе может быть исполь­зо­ва­на, что­бы пока­зать, что пол­ный граф K7 с семью вер­ши­на­ми не явля­ет­ся 1‑планарным, посколь­ку этот граф име­ет 21 реб­ро, а тогда 4n − 8 = 20 < 21 [7].

Гово­рят, что 1‑планарный граф явля­ет­ся опти­маль­ным 1‑планарным гра­фом, если он име­ет в точ­но­сти 4n − 8 рёбер, мак­си­маль­но воз­мож­ное чис­ло. В 1‑планарном вло­же­нии опти­маль­но­го 1‑планарного гра­фа непе­ре­се­ка­ю­щи­е­ся рёб­ра обя­за­тель­но обра­зу­ют раз­би­е­ние на четы­рёх­уголь­ни­ки (т.е. обра­зу­ют поли­эд­раль­ный граф, в кото­ром каж­дая грань явля­ет­ся четы­рёх­уголь­ни­ком). Любое раз­би­е­ние на четы­рёх­уголь­ни­ки порож­да­ет 1‑планарный граф путём добав­ле­ния двух диа­го­на­лей в каж­дую квад­рат­ную грань. Отсю­да сле­ду­ет, что любой опти­маль­ный 1‑планарный граф явля­ет­ся эйле­ро­вым (все его вер­ши­ны име­ют чёт­ную сте­пень), что наи­мень­шая сте­пень в таких гра­фах — 6, и что любой опти­маль­ный 1‑планарный граф име­ет по мень­шей мере восемь вер­шин со сте­пе­нью в точ­но­сти шесть. Кро­ме того, любой опти­маль­ный 1‑планарный граф вер­шин­но 4‑связен и любое 4‑вершинное сече­ние в таком гра­фе явля­ет­ся отсе­ка­ю­щим цик­лом в ниже­ле­жа­щем раз­би­е­нии на четы­рёх­уголь­ни­ки[8].

Гра­фы, име­ю­щие пря­мо­ли­ней­ные 1‑планарные рисун­ки (то есть рисун­ки, в кото­рых каж­дое реб­ро пред­став­ля­ет­ся пря­мо­ли­ней­ным отрез­ком и каж­дый отре­зок пере­се­ка­ет­ся мак­си­мум одним дру­гим реб­ром), име­ют слег­ка более силь­ную гра­ни­цу 4n − 9 мак­си­маль­но­го чис­ла рёбер, кото­рая дости­га­ет­ся на бес­ко­неч­ном чис­ле гра­фов[9].

Полные многодольные графы

1‑планарный рису­нок гра­фа кок­тейль-вече­рин­ки K2,2,2,2

Пол­ная клас­си­фи­ка­ция 1‑планарных пол­ных гра­фов, пол­ных дву­доль­ных гра­фов и более общих пол­ных мно­го­доль­ных гра­фов извест­на. Любой пол­ный дву­доль­ный граф вида K2,n явля­ет­ся 1‑планарным, как и любой пол­ный трёх­доль­ный граф вида K1,1,n. Кро­ме этих бес­ко­неч­ных мно­жеств, пол­ны­ми мно­го­доль­ны­ми 1‑планарными гра­фа­ми явля­ют­ся K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2 и их под­гра­фы. Мини­маль­ные пол­ные мно­го­доль­ные гра­фы, не явля­ю­щи­е­ся 1‑планарными, — это K3,7, K4,5, K1,3,4, K2,3,3, and K1,1,1,1,3.
Напри­мер, пол­ный дву­доль­ный граф K3,6 явля­ет­ся 1‑планарным, посколь­ку он явля­ет­ся под­гра­фом K1,1,1,6, а вот K3,7 не явля­ет­ся 1‑планарным[7].

Вычислительная сложность

Про­вер­ка, явля­ет­ся ли граф 1‑планарным, NP-пол­на[10][11], и зада­ча оста­ёт­ся NP-пол­ной даже для гра­фов, полу­чен­ных из пла­нар­ных гра­фов путём добав­ле­ния един­ствен­но­го реб­ра[12] и для гра­фов огра­ни­чен­ной шири­ны[en][13].

Зада­ча фик­си­ро­ван­но-пара­мет­ри­че­ски раз­ре­ши­ма[en], если пара­мет­ри­зо­вать по цик­ло­ма­ти­че­ско­му чис­лу или по глу­бине дере­ва, так что она может быть реше­на за поли­но­ми­аль­ное вре­мя, если эти пара­мет­ры огра­ни­че­ны[13].

В отли­чие от тео­ре­мы Фари для пла­нар­ных гра­фов, не все 1‑планарные гра­фы могут быть нари­со­ва­ны 1‑планарно с отрез­ка­ми пря­мой в каче­стве рёбер[14][15]. Одна­ко про­вер­ка, мож­но ли нари­со­вать 1‑планарный граф с пря­мы­ми рёб­ра­ми, может быть выпол­не­на за поли­но­ми­аль­ное вре­мя[16]. Кро­ме того, любой вер­шин­но 3‑связный 1‑планарный граф име­ет 1‑планарный рису­нок, в кото­ром мак­си­мум одно реб­ро на внеш­ней гра­ни име­ет излом. Такой рису­нок может быть постро­ен за линей­ное вре­мя, исхо­дя из 1‑планарного вло­же­ния гра­фа[17]. 1‑планарные гра­фы име­ют огра­ни­чен­ную книж­ную тол­щи­ну[18], но неко­то­рые 1‑планарные гра­фы, вклю­чая K2,2,2,2, име­ют книж­ную тол­щи­ну по мень­шей мере четы­ре[19].

1‑планарные гра­фы име­ют огра­ни­чен­ную локаль­ную дре­вес­ную шири­ну, что озна­ча­ет, что суще­ству­ет (линей­ная) функ­ция f, такая, что 1‑планарные гра­фы диа­мет­ра d име­ют дре­вес­ную шири­ну, не пре­вос­хо­дя­щую f(d). То же свой­ство име­ет место для более общих гра­фов, кото­рые мож­но вло­жить в поверх­ность огра­ни­чен­но­го рода с огра­ни­чен­ным чис­лом пере­се­че­ний на реб­ро. Они так­же име­ют сепа­ра­то­ры, неболь­шое мно­же­ство вер­шин, уда­ле­ние кото­рых раз­би­ва­ет граф на связ­ные ком­по­нен­ты, раз­мер кото­рых состав­ля­ет посто­ян­ную дроб­ную часть от все­го гра­фа. Опи­ра­ясь на эти свой­ства мно­го­чис­лен­ные алго­рит­мы для пла­нар­ных гра­фов, такие как тех­ни­ка Брен­ды Бей­кер (Brenda Sue Baker – аме­ри­кан­ская жен­щи­на-мате­ма­тик ) для постро­е­ния аппрок­си­ма­ци­он­ных алго­рит­мов, могут быть рас­ши­ре­ны для 1‑планарных гра­фов. Напри­мер, этот метод при­во­дит к при­бли­жен­ной схе­ме поли­но­ми­аль­но­го вре­ме­ни для нахож­де­ния наи­боль­ше­го неза­ви­си­мо­го мно­же­ства 1‑планарного гра­фа[20].

Обобщения и связанные концепции

Класс гра­фов, ана­ло­гич­ных внеш­не­пла­нар­ным гра­фам для 1‑планарности, назы­ва­ет­ся внешне 1‑планарные гра­фы. Это гра­фы, кото­рые мож­но нари­со­вать на дис­ке с вер­ши­на­ми на гра­ни­це дис­ка и с рёб­ра­ми, име­ю­щи­ми мак­си­мум одно пере­се­че­ние на реб­ро. Эти гра­фы все­гда могут быть нари­со­ва­ны (в виде внешне 1‑планарного гра­фа) с пря­мы­ми рёб­ра­ми и пере­се­че­ни­я­ми под пря­мы­ми угла­ми[21]. При помо­щи дина­ми­че­ско­го про­грам­ми­ро­ва­ния на SPQR-дере­ве задан­но­го гра­фа мож­но про­ве­рить, не явля­ет­ся ли граф внешне 1‑планарным, за линей­ное вре­мя[22][23]. Трёх­связ­ные ком­по­нен­ты гра­фа (узлы дере­ва SPQR) могут состо­ять толь­ко из цик­лов, бондгра­фов и пол­ных гра­фов с четырь­мя вер­ши­на­ми, отку­да сле­ду­ет, что внешне 1‑планарные гра­фы явля­ют­ся пла­нар­ны­ми и име­ют дре­вес­ную шири­ну мак­си­мум три. В отли­чие от 1‑планарных гра­фов, внешне 1‑планарные гра­фы име­ют харак­те­ри­за­цию в тер­ми­нах мино­ров гра­фа — граф явля­ет­ся внешне 1‑планарным тогда и толь­ко тогда, когда в нём нет ни одно­го из пяти запре­щён­ных мино­ров[23].

Клас­су 1‑планарных гра­фов при­над­ле­жат гра­фы 4‑карт[en], гра­фы, обра­зо­ван­ные из смеж­ных реги­о­нов плос­ко­сти с усло­ви­ем, что ника­кая точ­ка не лежит на гра­ни­це более четы­рёх реги­о­нов (вер­ши­ны (реги­о­ны) соеди­не­ны реб­ром, если реги­о­ны гра­ни­чат). И обрат­но — любой опти­маль­ный 1‑планарный граф явля­ет­ся гра­фом 4‑карты. Одна­ко 1‑планарные гра­фы, не явля­ю­щи­е­ся опти­маль­ны­ми 1‑планарными, могут и не быть гра­фа­ми карт[24].

1‑планарные гра­фы обоб­ща­ют­ся до k-пла­нар­ных гра­фов, в кото­рых каж­дое реб­ро пере­се­ка­ет­ся дру­ги­ми рёб­ра­ми не более k раз. Рин­гель опре­де­лил локаль­ное чис­ло пере­се­че­ний гра­фа G как наи­мень­шее неот­ри­ца­тель­ное k, такое, что G име­ет k-пла­нар­ный рису­нок. Посколь­ку локаль­ное чис­ло пере­се­че­ний рав­но наи­боль­шей сте­пе­ни гра­фа пере­се­че­ний рёбер опти­маль­но­го рисун­ка, а тол­щи­на (мини­маль­ное чис­ло пла­нар­ных гра­фов, на кото­рые мож­но раз­ло­жить рёб­ра) может рас­смат­ри­вать­ся как хро­ма­ти­че­ское чис­ло гра­фа пере­се­че­ний под­хо­дя­ще­го рисун­ка, из тео­ре­мы Брук­са сле­ду­ет, что тол­щи­на не боль­ше чем на еди­ни­цу пре­вы­ша­ет локаль­ное чис­ло пере­се­че­ний[25]. k-пла­нар­ные гра­фы с n вер­ши­на­ми име­ют мак­си­мум O(k1⁄2n) рёбер[26] и дре­вес­ную шири­ну O((kn)1⁄2)[27]. Неглу­бо­кий минор k-пла­нар­но­го гра­фа с глу­би­ной d сам явля­ет­ся (2d + 1)k-пла­нар­ным, так что неглу­бо­кие мино­ры 1‑планарных гра­фов и k-пла­нар­ных гра­фов явля­ют­ся раз­ре­жен­ны­ми гра­фа­ми, здесь име­ет­ся в виду, что 1‑планарные и k-пла­нар­ные гра­фы име­ют огра­ни­чен­ное рас­ше­ри­ние[en][28].

Для непла­нар­ных гра­фов так­же мож­но задать пара­метр чис­ло пере­се­че­ний, мини­маль­ное чис­ло рёбер, кото­рые пере­се­ка­ют­ся в любом рисун­ке гра­фа. Граф с чис­лом пере­се­че­ний k обя­за­тель­но k-пла­на­рен, но обрат­ное не обя­за­тель­но вер­но. Напри­мер, Граф Хиву­да име­ет чис­ло пере­се­че­ний 3, но не обя­за­тель­но эти пере­се­че­ния долж­ны быть с одним реб­ром, он 1‑планарен и может быть нари­со­ван с одно­вре­мен­ной опри­ми­за­ци­ей обще­го чис­ла пере­се­че­ний и пере­се­че­ний на одно реб­ро.

Дру­гое свя­зан­ное поня­тие для непла­нар­ных гра­фов — пере­кос[en], мини­маль­ное чис­ло рёбер, кото­рые нуж­но уда­лить, что­бы сде­лать граф пла­нар­ным.

Примечания

  1. ↑ Ringel, 1965, с. 107–117.
  2. ↑ 1 2 Боро­дин, 1984, с. 12–26, 108.
  3. ↑ Albertson, Mohar, 2006, с. 289–295.
  4. ↑ Schumacher, 1986, с. 291–300.
  5. ↑ Czap, Hudák, 2013.
  6. ↑ Brandenburg, Eppstein и др., 2013.
  7. ↑ 1 2 Czap, Hudák, 2012, с. 505–512.
  8. ↑ Suzuki, 2010, с. 1527–1540.
  9. ↑ Didimo, 2013, с. 236–240.
  10. ↑ Grigoriev, Bodlaender, 2007, с. 1–11.
  11. ↑ Korzhik, Mohar, 2009, с. 302–312.
  12. ↑ Cabello, Mohar, 2012.
  13. ↑ 1 2 Bannister, Cabello, Eppstein, 2013.
  14. ↑ Eggleton, 1986, с. 149–172.
  15. ↑ Thomassen, 1988, с. 335–341.
  16. ↑ Hong, Eades, Liotta, Poon, 2012, с. 335–346.
  17. ↑ Alam, Brandenburg, Kobourov, 2013, с. 83–94.
  18. ↑ Bekos, Bruckdorfer, Kaufmann, Raftopoulou, 2015, с. 130–141.
  19. ↑ Bekos, Kaufmann, Zielke, 2015, с. 113–125.
  20. ↑ Grigoriev, Bodlaender, 2007. Гри­го­рьев и Бод­ла­ен­дер фор­му­ли­ро­ва­ли свои резуль­та­ты для гра­фов с извест­ным 1‑планарным вло­же­ни­ем и исполь­зо­ва­ли дре­вес­ное раз­ло­же­ние вло­же­ния с пере­се­че­ни­я­ми, заме­нён­ны­ми на вер­ши­ны сте­пе­ни четы­ре. Одна­ко их мето­ды напря­мую могут быть при­ме­не­ны для исход­но­го 1‑планарного гра­фа с огра­ни­чен­ной локаль­ной дре­вес­ной шири­ной, что поз­во­ля­ет при­ме­нить метод Бей­кер к ним пря­мо, не зная зара­нее вло­же­ния.
  21. ↑ Dehkordi, Eades, 2012, с. 543–557.
  22. ↑ Hong, Eades и др., 2013, с. 71–82.
  23. ↑ 1 2 Auer, Bachmaier и др., 2013, с. 107–118.
  24. ↑ Chen, Grigni, Papadimitriou, 2002, с. 127–138.
  25. ↑ Kainen, 1973, с. 88–95.
  26. ↑ Pach, Tóth, 1997, с. 427–439.
  27. ↑ Dujmović, Eppstein, Wood, 2015, с. 77–88.
  28. ↑ Nešetřil, Ossona de Mendez, 2012, с. 321, Theorem 14.4.

Литература

  • Gerhard Ringel. Ein Sechsfarbenproblem auf der Kugel (нем.) // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1965. — Bd. 29. — S. 107–117. — doi:10.1007/BF02996313.
  • Michael O. Albertson, Bojan Mohar. Coloring vertices and faces of locally planar graphs // Graphs and Combinatorics. — 2006. — Т. 22, вып. 3. — С. 289–295. — doi:10.1007/s00373-006‑0653‑4.
  • H. Schumacher. Zur Struktur 1‑planarer Graphen (нем.) // Mathematische Nachrichten. — 1986. — Bd. 125. — S. 291–300.
  • Július Czap, Dávid Hudák. On drawings and decompositions of 1‑planar graphs // Electronic Journal of Combinatorics. — 2013. — Т. 20, вып. 2.
  • Franz Josef Brandenburg, David Eppstein, Andreas Gleißner, Michael T. Goodrich, Kathrin Hanauer, Josef Reislhuber. Proc. 20th Int. Symp. Graph Drawing / Walter Didimo, Maurizio Patrignani. — 2013.
  • Yusuke Suzuki. Re-embeddings of maximum 1‑planar graphs // SIAM Journal on Discrete Mathematics. — 2010. — Т. 24, вып. 4. — С. 1527–1540. — doi:10.1137/090746835.
  • Walter Didimo. Density of straight-line 1‑planar graph drawings // Information Processing Letters. — 2013. — Т. 113, вып. 7. — С. 236–240. — doi:10.1016/j.ipl.2013.01.013.
  • Július Czap, Dávid Hudák. 1‑planarity of complete multipartite graphs // Discrete Applied Mathematics. — 2012. — Т. 160, вып. 4–5. — С. 505–512. — doi:10.1016/j.dam.2011.11.014.
  • Alexander Grigoriev, Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge // Algorithmica. — 2007. — Т. 49, вып. 1. — С. 1–11. — doi:10.1007/s00453-007‑0010‑x.
  • Vladimir P. Korzhik, Bojan Mohar. Graph Drawing: 16th International Symposium, GD 2008, Heraklion, Crete, Greece, September 21–24, 2008, Revised Papers / Ioannis G. Tollis, Maurizio Patrignani. — Springer, 2009. — Т. 5417. — С. 302–312. — (Lecture Notes in Computer Science). — doi:10.1007/978–3‑642–00219-9_29.
  • Sergio Cabello, Bojan Mohar. Adding one edge to planar graphs makes crossing number and 1‑planarity hard. — 2012. — arXiv:1203.5944. Рас­ши­рен­ная вер­сия ста­тьи 17-го ACM Сим­по­зи­у­ма по Вычис­ли­тель­ной гео­мет­рии, 2010.
  • Michael J. Bannister, Sergio Cabello, David Eppstein. Algorithms and Data Structures Symposium (WADS 2013). — 2013.
  • Michael Bekos, Michael Kaufmann, Christian Zielke. Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015). — 2015. — С. 113–125.
  • Vida Dujmović, David Eppstein, David R. Wood. Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015). — 2015. — С. 77–88.
  • О.В. Боро­дин. Реше­ние зада­чи Рин­ге­ля о вер­шин­но-гра­не­вой рас­крас­ке плос­ких гра­фов и о рас­крас­ке 1‑планарных гра­фов. // Мето­ды дис­крет­но­го ана­ли­за в изу­че­нии реа­ли­за­ций логи­че­ских функ­ций. — Ново­си­бирск: Инсти­тут мате­ма­ти­ки СО АН СССР, 1984. — Вып. 41. — С. 12–26, 108.
  • Roger B. Eggleton. Rectilinear drawings of graphs // Utilitas Mathematica. — 1986. — Т. 29. — С. 149–172.
  • Carsten Thomassen. Rectilinear drawings of graphs // Journal of Graph Theory. — 1988. — Т. 12, вып. 3. — С. 335–341. — doi:10.1002/jgt.3190120306.
  • Seok-Hee Hong, Peter Eades, Giuseppe Liotta, Sheung-Hung Poon. Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20–22, 2012, Proceedings / Joachim Gudmundsson, Julián Mestre, Taso Viglas. — Springer, 2012. — Т. 7434. — С. 335–346. — (Lecture Notes in Computer Science). — doi:10.1007/978–3‑642–32241-9_29.
  • Md. Jawaherul Alam, Franz J. Brandenburg, Stephen G. Kobourov. Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23–25, 2013, Revised Selected Papers. — 2013. — Т. 8242. — С. 83–94. — (Lecture Notes in Computer Science). — doi:10.1007/978–3‑319–03841-4_8.
  • Michael A. Bekos, Till Bruckdorfer, Michael Kaufmann, Chrysanthi Raftopoulou. Algorithms – ESA 2015. — Springer, 2015. — Т. 9294. — С. 130–141. — (Lecture Notes in Computer Science). — doi:10.1007/978–3‑662–48350-3_12.
  • Hooman Reisi Dehkordi, Peter Eades. Every outer-1-plane graph has a right angle crossing drawing // International Journal of Computational Geometry & Applications. — 2012. — Т. 22, вып. 6. — С. 543–557. — doi:10.1142/S021819591250015X.
  • Seok-Hee Hong, Peter Eades, Naoki Katoh, Giuseppe Liotta, Pascal Schweitzer, Yusuke Suzuki. 21st International Symposium, GD 2013, Bordeaux, France, September 23–25, 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff. — 2013. — Т. 8242. — С. 71–82. — (Lecture Notes in Computer Science). — doi:10.1007/978–3‑319–03841-4_7.
  • Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber. 21st International Symposium, GD 2013, Bordeaux, France, September 23–25, 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff. — 2013. — Т. 8242. — С. 107–118. — (Lecture Notes in Computer Science). — doi:10.1007/978–3‑319–03841-4_10.
  • Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. Map graphs // Journal of the ACM. — 2002. — Т. 49, вып. 2. — С. 127–138. — doi:10.1145/506147.506148.
  • Paul Kainen. Thickness and coarseness of graphs // Abh. Math. Sem. Univ. Hamburg. — 1973. — Т. 39. — С. 88–95. — doi:10.1007/BF02992822.
  • János Pach, Géza Tóth. Graphs drawn with few crossings per edge // Combinatorica. — 1997. — Т. 17, вып. 3. — С. 427–439. — doi:10.1007/BF01215922.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — С. 321, Theorem 14.4. — (Algorithms and Combinatorics). — ISBN 978–3‑642–27874‑7. — doi:10.1007/978–3‑642–27875‑4.


Источ­ник — https://ru.wikipedia.org/w/index.php?title=1‑планарный_граф&oldid=124946209
[btn-action]
[wp-post-stars]

Похожее ...

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Учи русский с сайтом "РЯ"
- время проведешь не зря!

Recent Comments

Нет комментариев для просмотра.

Поиск