Test de planarité

En théorie des graphes, le problème du test de planarité est le problème algorithmique qui consiste à tester si un graphe donné est un graphe planaire (c'est-à-dire s'il peut être dessiné dans le plan sans intersection d'arêtes). Il s'agit d'un problème bien étudié en informatique pour lequel de nombreux algorithmes pratiques ont été donnés, souvent en décrivant de nouvelles structures de données. La plupart de ces méthodes fonctionnent en temps O(n) (temps linéaire), où n est le nombre d'arêtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal. La sortie d'un algorithme de test de planarité, plutôt que d'être simplement une valeur booléenne (le graphe est-il planaire, oui ou non ?), peut être un plongement du graphe dans le plan si le graphe est planaire, ou la donnée d'un obstacle à la planarité tel qu'un sous-graphe de Kuratowski s'il ne l'est pas.

Critères de planarité

Les graphes K3,3 et K5.

Les algorithmes de test de planarité tirent généralement parti des théorèmes de la théorie des graphes qui caractérisent l'ensemble des graphes planaires en termes indépendants du dessin de graphes. Ces critères comprennent notamment :

Le critère de planarité de Fraysseix-Rosenstiehl peut être utilisé directement dans le cadre des algorithmes de test de planarité, tandis que les théorèmes de Kuratowski et Wagner sont des applications indirectes : si un algorithme peut trouver une copie de K5 ou K3,3 dans un graphe donné, cela prouve que le graphe d'entrée n'est pas planaire et il retourne sans calcul supplémentaire.

D'autres critères de planarité, qui caractérisent mathématiquement les graphes planaires mais sont moins centraux pour les algorithmes de test de planarité, comprennent :

Algorithmes

Méthode d'addition de chemins

La méthode maintenant classique d'addition de chemins de Hopcroft et Tarjan été le premier algorithme de test de planarité en temps linéaire publié en 1974[1]. Robert Cori a décrit l'historique et les principes de cet algorithme dans un article paru en 2014 dans le Bulletin de la société informatique de France[2] où il mentionne l'activité française dans ce domaine à peu près à la même époque. Une implémentation des algorithmes de Hopcroft et Tarjan est fournie dans la Library of Efficient Data types and Algorithms (en) de Mehlhorn, Mutzel et Näher[3],[4]. En 2012, Taylor[5] a étendu cet algorithme pour générer toutes les permutations d'ordre cyclique des arêtes pour les plongements planaires de composantes biconnexes.

Méthode d'addition de sommets

Les méthodes d'addition de sommets opèrent en maintenant une structure de données représentant les plongements possibles d'un sous-graphe induit du graphe donné, et en ajoutant les sommets un par un à cette structure de données. Ces méthodes ont commencé avec une méthode en O (n 2) conçue par Lempel, Even et Cederbaum en 1967[6]. Elle a été améliorée par Even et Tarjan[7] en 1976, qui ont trouvé une solution en temps linéaire pour l'étape de numérotation st, et par Booth et Lueker[8], qui ont développé la structure de données d'arbre PQ. Avec ces améliorations, l'algorithme est linéaire et surpasse la méthode d'addition de chemins dans la pratique[9] . Cette méthode a également été étendue pour permettre un calcul efficace d'un plongement planaire (dessin) d'un graphe planaire[10] . En 1999, Shih et Hsu ont simplifié ces méthodes en utilisant un arbre PC (une variante non enracinée des arbres PQ) et un parcours d'arbre postfixe de l'arbre de recherche en profondeur des sommets[11].

Méthode d'addition d'arêtes

En 2004, John Boyer et Wendy Myrvold[12] ont développé un algorithme simplifié en temps linéaire, inspiré à l'origine de la méthode de l'arbre PQ, qui se libère de l'arbre PQ et utilise des adjonctions d'arêtes pour calculer un plongement planaire, s'il existe. Sinon, une subdivision de Kuratowski (de K 5 ou K 3,3 ) est calculée. Il s'agit de l'un des deux algorithmes les plus récents (l'autre est l'algorithme de test de planarité de de Fraysseix, de Mendez et Rosenstiehl[13]. Le test de Boyer-Myrvold a été étendu pour extraire plusieurs subdivisions de Kuratowski d'un graphe d'entrée non planaire en un temps d'exécution linéairement dépendant de la taille de sortie[14]. Le code source du test de planarité [15],[16] et de l'extraction des subdivisions de Kuratowski est public. Un autre algorithme est donné par Bernhard Haeupler et Robert E. Tarjan[17]. D'autres algorithmes qui localisent un sous-graphe de Kuratowski en temps linéaire ont été développés par Williamson dans les années 1980[18].

Méthode de séquence de construction

Une méthode différente utilise une construction inductive de graphes 3-connexes pour construire de façon incrémentale des plongements planaires de chaque composante 3-connexe du graphe donné (et donc un plongement planaire du graphe lui-même)[19]. La construction commence par K4 et est définie de telle manière que chaque graphe intermédiaire vers une composante complète est à nouveau 3-connexe. Étant donné que ces graphes ont un plongement unique (au retournement et au choix de la face externe près), le graphe suivant, s'il est toujours planaire, doit être un raffinement du graphe précédent. Cela permet de réduire le test de planéité au test, à chaque étape, si l'arête suivante ajoutée a ses deux extrémités sur la face externe du plongement courant. Bien que conceptuellement très simple (et en temps linéaire), la méthode elle-même est compliquée par la difficulté de trouver la séquence de construction.

Variantes et extensions

La recherche continue à être active sur des variantes, concernant à la fois la parallélisation et la distribution sur plusieurs sites, et sur des familles particulières de graphes; voici un échantillon :

  • Giuseppe Liotta, Ignaz Rutter et Alessandra Tappini, « Simultaneous FPQ-Ordering and Hybrid Planarity Testing », SOFSEM,‎ , p. 617-626.
  • Seok-Hee Hong et Hiroshi Nagamochi, « A linear-time algorithm for testing full outer-2-planarity », Discret. Appl. Math., vol. 255,‎ , p. 234-257.
  • Guy Barshap et Tamir Tassa, « Privacy-Preserving Planarity Testing of Distributed Graphs », Trans. Data Priv., vol. 12, no 2,‎ , p. 117-144.

Un autre sujet est la variante dynamique des algorithmes : tester la planarité d'un graphe qui évolue par adjonction et suppression de sommets ou d'arêtes : Étant donné un graphe dynamique, sujet à des insertions et des suppressions d'arêtes, la question est de savoir si le graphe admet couramment une représentation planaire. Les auteurs donnent un algorithme déterministe entièrement dynamique pour les graphes généraux, fonctionnant en temps amorti par insertion ou suppression d'arêtes, qui maintient un bit indiquant si le graphe est actuellement planaire ou non. C'est une amélioration du meilleur algorithme précédent, de 1996, et dû à Eppstein, Galil, Italiano, Spencer qui demande un temps amorti par mise à jour.

  • David Eppstein, Zvi Galil, Giuseppe F. Italiano et Thomas H. Spencer, « Separator Based Sparsification: I. Planarity Testing and Minimum Spanning Trees », Journal of Computer and Systems Sciences, vol. 52, no 1,‎ , p. 3-27
  • Zvi Galil, Giuseppe F. Italiano et Neil Sarnak, « Fully Dynamic Planarity Testing with Applications », Journal of the ACM, vol. 46, no 1,‎ , p. 28-91
  • Jacob Holm et Eva Rotenberg, « Fully-dynamic planarity testing in polylogarithmic time », STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing,‎ , p. 167–180 (DOI 10.1145/3357713.3384249)

Une présentation est donnée dans Quanta Magazine[20]

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Planarity testing » (voir la liste des auteurs).
  1. John Hopcroft et Robert E. Tarjan, « Efficient planarity testing », Journal of the Association for Computing Machinery, vol. 21, no 4,‎ , p. 549–568 (DOI 10.1145/321850.321852, hdl 1813/6011 Accès libre).
  2. Robert Cori, « L'algorithme de test de planarité de R. E. Tarjan », 1024– Bulletin de la société informatique de France, no 4,‎ , p. 55-65 (ISSN 2270-1419, lire en ligne, consulté le ).
  3. Kurt Mehlhorn et Petra Mutzel, « On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm », Algorithmica, vol. 16, no 2,‎ , p. 233–242 (DOI 10.1007/bf01940648, hdl 11858/00-001M-0000-0014-B51D-B Accès libre)
  4. Kurt Mehlhorn et Stefan Näher, « LEDA: A library of efficient data types and algorithms », Communications of the ACM, vol. 38, no 1,‎ , p. 96–102 (DOI 10.1145/204865.204889, CiteSeerx 10.1.1.54.9556)
  5. Martyn G. Taylor, Planarity Testing by Path Addition, University of Kent, (lire en ligne) — Thèse de Ph. D.
  6. Abraham Lempel, Shimon Even et I. Cederbaum, « An algorithm for planarity testing of graphs », dans Pierre Rosenstiehl, Theory of Graphs, New York, Gordon and Breach, , p. 215–232.
  7. Shimon Even et Robert E. Tarjan, « Computing an st-numbering », Theoretical Computer Science, vol. 2, no 3,‎ , p. 339–344 (DOI 10.1016/0304-3975(76)90086-4).
  8. Kellogg S. Booth et George S. Lueker, « Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms », J. Comput. Syst. Sci., vol. 13, no 3,‎ , p. 335-379.
  9. Boyer et Myrvold 2004, p. 243: “Its implementation in LEDA is slower than LEDA implementations of many other O(n)-time planarity algorithms.”
  10. Norishige Chiba, Takao Nishizeki, Shigenobu Abe et Takao Ozawa, « A linear algorithm for embedding planar graphs using PQ–trees », Journal of Computer and System Sciences, vol. 30, no 1,‎ , p. 54–76 (DOI 10.1016/0022-0000(85)90004-2).
  11. Wei-Kuan Shih Shih et Wen-Lian Hsu, « A new planarity test », Theoretical Computer Science, vol. 223, nos 1–2,‎ , p. 179–191 (DOI 10.1016/S0304-3975(98)00120-0).
  12. John M. Boyer et Wendy J. Myrvold, « On the cutting edge: simplified O(n) planarity by edge addition », Journal of Graph Algorithms and Applications, vol. 8, no 3,‎ , p. 241–273 (DOI 10.7155/jgaa.00091, lire en ligne).
  13. Hubert de Fraysseix, Patrice Ossona de Mendez et Pierre Rosenstiehl, « Trémaux Trees and Planarity », International Journal of Foundations of Computer Science, vol. 17, no 5,‎ , p. 1017–1030 (DOI 10.1142/S0129054106004248, arXiv math/0610935).
  14. Markus Chimani, Petra Mutzel et Jens M. Schmidt, « Efficient extraction of multiple Kuratowski subdivisions », Symposium on Graph Drawing (GD'07), Sydney, Australia, Springer-Verlag,‎ , p. 159–170.
  15. « OGDF - Open Graph Drawing Framework: Start »
  16. « Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding - 1.40.0 »
  17. Bernhard Haeupler et Robert E. Tarjan, « Planarity Algorithms via PQ-Trees (Extended Abstract) », Electronic Notes in Discrete Mathematics, vol. 31,‎ , p. 143–149 (DOI 10.1016/j.endm.2008.06.029)
  18. S. G. Williamson, « Depth First Search and Kuratowski Subgraphs », Journal of the ACM, vol. 31, no 4,‎ , p. 681–693 (DOI 10.1145/1634.322451).
  19. Jens M. Schmidt, « The Mondshein Sequence », Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14),‎ , p. 967–978 (ISBN 978-3-662-43947-0, DOI 10.1007/978-3-662-43948-7_80).
  20. Stephanie DeMarco, « A New Algorithm for Graph Crossings, Hiding in Plain Sight », (consulté le ).

Read other articles:

Halaman ini berisi artikel tentang pulau. Untuk informasi lebih rinci tentang Antigua sebagai entitas politik, lihat Antigua dan Barbuda. Untuk tempat lain bernama Antigua, lihat Antigua (disambiguasi). Untuk kota di Guatemalan, lihat Antigua Guatemala. AntiguaNama lokal: WaladliPeta Antigua dan parokinyaGeografiLokasiLaut KaribiaKoordinat17°5′N 61°48′W / 17.083°N 61.800°W / 17.083; -61.800Koordinat: 17°5′N 61°48′W / 17.083°N 61.800°W&#x...

 

Diane LanePekerjaanAktrisTahun aktif1979–sekarangSuami/istriChristopher Lambert (1988–1994)Josh Brolin (2004–2013)Situs webhttp://www.dianelane.com/ (offline) Diane Lane (lahir 22 Januari 1965) adalah seorang aktris berkebangsaan Amerika Serikat. Ia memulai kariernya sejak tahun 1979. Filmografi Tahun Film Sebagai Keterangan lain 1979 A Little Romance Lauren King 1980 Touched by Love Karen Aka To Elvis, with Love 1981 Great Performances Charity Royall TV (1 episode) Ladies and Gen...

 

2004 French filmThe LightTheatrical release posterL'ÉquipierDirected byPhilippe LioretWritten byPhilippe Lioret Emmanuel Courcol Christian SinnigerProduced byChristophe RossignonStarringGrégori DerangèreSandrine BonnairePhilippe TorretonÉmilie DequenneCinematographyPatrick BlossierEdited byMireille LeroyMusic byNicola PiovaniDistributed byMars FilmsRelease date 3 November 2004 (2004-11-03) Running time94 minutesCountryFranceLanguageFrenchBudget$7.6 millionBox office$5.2 mil...

Donald Trump (kiri) and Billy Bush (kanan) terekam dalam percakapan yang sangat cabul tentang wanita pada tahun 2005. Rekaman dirilis pada Oktober 2016, saat Trump menjadi calon presiden Amerika Serikat. Artikel ini bagian dariseri tentangDonald Trump Presiden Amerika Serikat Kepresidenan Transisi Pelantikan Garis waktu Keputusan eksekutif proklamasi pengampunan Perjalanan 2017 2018 2019 internasional KTT Riyadh Singapura Helsinki Hanoi DMZ Penutupan Jan 2018 2018–2019 Jajak pendapat Unjuk...

 

Radio stationNPO Radio 5Broadcast areaNetherlandsProgrammingFormatClassic hits (1950s-today)OwnershipOwnerNPOSister stationsNPO Radio 1NPO Radio 2NPO 3FMNPO KlassiekNPO Radio 2 Soul & JazzFunXHistoryFirst air date2 October 1983 (as Hilversum 5)Former call signsHilversum 5LinksWebcastRadioplayerWebsitewww.radio5.nl Radio 5 logo used until 2014. NPO Radio 5 is a Dutch public-service network radio station operated by NPO. Its main format is classic hits (both English and Dutch titles) from t...

 

Pour un article plus général, voir Tour de France 2021. 18e étape du Tour de France 2021 GénéralitésCourse18e étape، Tour de France 2021Type Étape de montagneDate15 juillet 2021Distance129,7 kmPays FranceLieu de départPauLieu d'arrivéeLuz-ArdidenPartants144Arrivants144Vitesse moyenne36,407 km/hDénivelé3 555 mRésultats de l’étape1er Tadej Pogačar3 h 33 min 45 s(UAE Team Emirates)2e Jonas Vingegaard+ 2 s3e Richard Carapaz+ 2 s David Gaudu(Groupama-FDJ)Classement généra...

Sophie Grégoire Trudeau, married to Justin Trudeau The spouse of the prime minister of Canada (French: époux du premier ministre du Canada) is the wife or husband of the prime minister of Canada. Sophie Grégoire Trudeau is married to the 23rd and current prime minister, Justin Trudeau,[1] though the couple have been separated since August 2, 2023.[2] Nineteen women have been wives of prime ministers of Canada; Kim Campbell, the only female prime minister, was unmarried dur...

 

Seekor kucing bersantai di sebuah pohon kucing buatan sendiri yang terdiri dari alas karpet, jalur landai, kotak, dan tali sisal. Pohon kucing (disebut juga sebagai rumah pohon kucing, kondominium kucing, atau stan kucing) adalah struktur buatan khusus untuk kucing yang berfungsi sebagai tempat bermain, berolahraga, dan bersantai. Deskripsi Pohon kucing memiliki tinggi yang bervariasi dan kucing lebih suka memilih yang cukup tinggi yang memungkinkan mereka untuk melihat apa saja dari atas. Ku...

 

Artikel ini bukan mengenai Austral Líneas Aéreas. Air Austral IATA ICAO Kode panggil UU REU REUNION Didirikan1974; 50 tahun lalu (1974) (oleh Gerard Etheve)Penghubung• Bandar Udara Internasional Roland Garros, Réunion • Bandar Udara Pierrefonds, RéunionKota fokusBandar Udara Internasional Dzaoudzi Pamandzi, MayotteProgram penumpang setiaCapricornAliansiVanilla AllianceAnak perusahaanEwa AirArmada8[1]Tujuan17Kantor pusatBandar Udara Internasional Roland Garros, Sainte-Mari...

English football manager A. H. Albut Personal informationFull name Alfred Hubert AlbutDate of birth 1849Place of birth Bromsgrove, Worcestershire, England[1]Date of death 1916 (aged 67)[2]Place of death Aston, WarwickshireManagerial careerYears Team1892–1900 Newton Heath Alfred Hubert Albut (1849–1916) was an English candy salesman[1] best known for being the first full-time employee of Newton Heath, the club now known as Manchester United.[3] He was made c...

 

Ancient name of Bahrain For the digital distribution company Artists Without A Label, see AWAL. For other uses, see Aval. Part of a series on the History of Bahrain Ancient Bahrain Dilmun Tylos Awal Historical region Islam in Bahrain Al-Ala'a Al-Hadrami Reigning Dynasties Qarmatians Uyunid dynasty Usfurid and Jarwanid dynasties Jabrid dynasty Portuguese occupation Muqrin ibn Zamil Antonio Correia Safavid hegemony 1717 Omani invasion of Bahrain 1783–1971 1783 Bani Utbah invasion of Bahrain P...

 

Steinbrunn-le-Hautcomune Steinbrunn-le-Haut – Veduta LocalizzazioneStato Francia RegioneGrand Est Dipartimento Alto Reno ArrondissementMulhouse CantoneBrunstatt TerritorioCoordinate47°40′N 7°21′E / 47.666667°N 7.35°E47.666667; 7.35 (Steinbrunn-le-Haut)Coordinate: 47°40′N 7°21′E / 47.666667°N 7.35°E47.666667; 7.35 (Steinbrunn-le-Haut) Superficie9,26 km² Abitanti609[1] (2009) Densità65,77 ab./km² Altre informazioniC...

STXBP5 المعرفات الأسماء المستعارة STXBP5, Tomosyn, LGL3, LLGL3, Nbla04300, syntaxin binding protein 5 معرفات خارجية الوراثة المندلية البشرية عبر الإنترنت 604586 MGI: MGI:1926058 HomoloGene: 16402 GeneCards: 134957 علم الوجود الجيني الوظيفة الجزيئية • ‏GO:0005097، ‏GO:0005099، ‏GO:0005100 GTPase activator activity• syntaxin-1 binding• syntaxin binding• myosin II binding المك�...

 

Disambiguazione – Se stai cercando altri significati, vedi John Milton (disambigua). (EN) «Descend from heav'n, Urania, by that nameIf rightly thou art called, whose voice divineFollowing, above th' Olympian hill I soar,Above the flight of Pegasean wing.» (IT) «Scendi, Urania, dal ciel, scendi, se questonome a te si convien, la cui divinavoce soave accompagnando, io m'ergosopra l'Olimpio monte e oltre il volodelle Pegásee favolose penne.» (John Milton, Paradiso perduto, Libro VII, vv....

 

هذه المقالة عن المجموعة العرقية الأتراك وليس عن من يحملون جنسية الجمهورية التركية أتراكTürkler (بالتركية) التعداد الكليالتعداد 70~83 مليون نسمةمناطق الوجود المميزةالبلد  القائمة ... تركياألمانياسورياالعراقبلغارياالولايات المتحدةفرنساالمملكة المتحدةهولنداالنمساأسترالي�...

Questa voce sull'argomento centri abitati del San Paolo è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Cosmoramacomune LocalizzazioneStato Brasile Stato federato San Paolo MesoregioneSão José do Rio Preto MicroregioneVotuporanga AmministrazioneSindacoClaudinei Monteiro Gil TerritorioCoordinate20°28′42″S 49°46′36″W / 20.478333°S 49.776667°W-20.478333; -49.776667�...

 

Kendo(剣道 kendō)FokussenjataKekerasansemi-kontakNegara asalJepangPenciptaNaganuma Sirōzaemon Kunisato (長沼 四郎左衛門 国郷), attributedOrang tuakenjutsuOlahraga olimpiktidak Kendo (剣道code: ja is deprecated , kendō) adalah seni bela diri modern dari Jepang yang menggunakan pedang. Kendo berasal dari kata ken (剣) yang artinya pedang, dan dō (道) yang artinya jalan. Jadi arti kendo secara keseluruhan adalah suatu jalan/proses disiplin diri yang membentuk suatu pribadi sam...

 

Use of the aesthetic feminism to promote organisationsThis article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) The neutrality of this article is disputed. Relevant discussion may be found on the talk page. Please do not remove this message until conditions to do so are met. (September 2018) (Learn how and when to remove this message) This article needs additional citations for verification. Please...

Le origini della guerra moderna sono da rintracciarsi nella guerra totale e nella diffusione delle armi nucleari, che prefigurano l'eventualità della devastazione globale del pianeta. L'opposto tipo di guerra moderna è il conflitto a bassa intensità, un fenomeno ampiamente documentato dopo la seconda guerra mondiale, tipicamente nella forma delle guerre per procura (in inglese proxy war), combattute nei confini regionali in senso geostrategico, con l'impiego delle cosiddette armi convenzio...

 

13th century Scottish prioress For other people named Bethóc, see Bethóc (disambiguation). The Iona Psalter, which may have been owned by Bethóc. Bethóc ingen Somairle[note 1] was a 13th-century Scottish prioress, considered to have been the first of Iona Nunnery. She was a daughter of Somairle mac Gilla Brigte. In about 1203, Bethóc's brother, Ragnall mac Somairle, founded the Benedictine Iona Abbey. Sometime afterwards, he founded the Augustinian nunnery on Iona. The precise fo...