ग्राफ एम्बेडिंग: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[File:Heawood graph and map on torus.png|thumb|[[हेवुड ग्राफ]]़ और संबंधित मानचित्र टोरस में सन्निहित है।]]




टोपोलॉजिकल ग्राफ सिद्धांत में, एक सतह <math>\Sigma</math> पर ग्राफ <math>G</math> का एक एम्बेडिंग (इम्बेडिंग भी लिखा जाता है) <math>\Sigma</math> पर <math>G</math> का एक प्रतिनिधित्व है जिसमें <math>\Sigma</math> के बिंदु शीर्षों और सरल चापों से जुड़े होते हैं ([0,1 की होमियोमोर्फिक छवियां) ]) किनारों से इस प्रकार जुड़े हुए हैं कि:


[[File:Heawood graph and map on torus.png|thumb|[[हेवुड ग्राफ]]़ और संबंधित मानचित्र टोरस में सन्निहित है।]]टोपोलॉजिकल ग्राफ़ सिद्धांत में, एक ग्राफ़ (असतत गणित) का एक एम्बेडिंग (इम्बेडिंग भी लिखा जाता है) <math>G</math> एक सतह पर (गणित) <math>\Sigma</math> का प्रतिनिधित्व है <math>G</math> पर <math>\Sigma</math> के किन बिंदुओं में <math>\Sigma</math> [[ग्राफ सिद्धांत]] और सरल चाप ([[होमियोमोर्फिज्म]] छवियां) से जुड़े हैं <math>[0,1]</math>) ग्राफ़ सिद्धांत से इस प्रकार जुड़े हैं कि:
*एक किनारे <math>e</math> से जुड़े चाप के अंतिम बिंदु <math>e,</math> के अंतिम शीर्ष से जुड़े बिंदु हैं।
 
* किसी भी चाप में अन्य शीर्षों से जुड़े बिंदु सम्मिलित नहीं हैं,
* एक किनारे से जुड़े चाप के अंतिम बिंदु <math>e</math> के अंतिम शीर्षों से जुड़े बिंदु हैं <math>e,</math>
* किसी भी चाप में अन्य शीर्षों से जुड़े बिंदु शामिल नहीं हैं,
* दो चाप कभी भी ऐसे बिंदु पर प्रतिच्छेद नहीं करते जो किसी भी चाप का आंतरिक भाग हो।
* दो चाप कभी भी ऐसे बिंदु पर प्रतिच्छेद नहीं करते जो किसी भी चाप का आंतरिक भाग हो।
यहाँ एक सतह एक [[सघन स्थान]] है, [[जुड़ा हुआ स्थान]] <math>2</math>-[[कई गुना]].
यहां एक सतह <math>2</math>-मैनिफोल्ड से जुड़ी एक कॉम्पैक्ट है।


अनौपचारिक रूप से, किसी ग्राफ़ को किसी सतह पर एम्बेड करना सतह पर ग्राफ़ को इस तरह से चित्रित करना है कि इसके किनारे केवल अपने अंतिम बिंदुओं पर ही प्रतिच्छेद कर सकें। यह सर्वविदित है कि किसी भी परिमित ग्राफ को 3-आयामी यूक्लिडियन अंतरिक्ष में एम्बेड किया जा सकता है <math>\mathbb{R}^3</math>.<ref name="3d-gd">{{citation
अनौपचारिक रूप से, किसी ग्राफ़ को किसी सतह पर एम्बेड करना सतह पर ग्राफ़ को इस तरह से चित्रित करना है कि इसके किनारे केवल अपने अंतिम बिंदुओं पर ही प्रतिच्छेद कर सकता है। यह सर्वविदित है कि किसी भी परिमित ग्राफ को 3-आयामी यूक्लिडियन स्पेस <math>\mathbb{R}^3</math> में एम्बेड किया जा सकता है।<ref name="3d-gd">{{citation
  | last1 = Cohen | first1 = Robert F.
  | last1 = Cohen | first1 = Robert F.
  | last2 = Eades | first2 = Peter | author2-link = Peter Eades
  | last2 = Eades | first2 = Peter | author2-link = Peter Eades
Line 25: Line 25:
  | year = 1995| isbn = 978-3-540-58950-1
  | year = 1995| isbn = 978-3-540-58950-1
  | doi-access = free
  | doi-access = free
  }}.</ref> एक [[समतलीय ग्राफ]] वह है जिसे 2-आयामी यूक्लिडियन अंतरिक्ष में एम्बेड किया जा सकता है <math>\mathbb{R}^2.</math>
  }}.</ref> एक समतल ग्राफ वह है जिसे 2-आयामी यूक्लिडियन स्पेस <math>\mathbb{R}^2.</math> में एम्बेड किया जा सकता है।
अक्सर, एम्बेडिंग को एक तुल्यता वर्ग (होमोमॉर्फिज्म के तहत) के रूप में माना जाता है <math>\Sigma</math>) अभी वर्णित प्रकार के अभ्यावेदन।


कुछ लेखक किनारों के लिए गैर-प्रतिच्छेदन स्थिति को छोड़कर ग्राफ एम्बेडिंग की परिभाषा के कमजोर संस्करण को परिभाषित करते हैं। ऐसे संदर्भों में सख्त परिभाषा को नॉन-क्रॉसिंग ग्राफ एम्बेडिंग के रूप में वर्णित किया गया है।<ref>{{citation|first1=Naoki|last1=Katoh|first2=Shin-ichi|last2=Tanigawa|title=Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings|publisher=Springer-Verlag|series=[[Lecture Notes in Computer Science]]|volume=4598|year=2007|pages=243–253|doi=10.1007/978-3-540-73545-8_25|chapter=Enumerating Constrained Non-crossing Geometric Spanning Trees|isbn=978-3-540-73544-1|citeseerx=10.1.1.483.874}}.</ref>
अक्सर, एक एम्बेडिंग को वर्णित प्रकार के अभ्यावेदन के समतुल्य वर्ग (<math>\Sigma</math> के होमोमोर्फिज्म के तहत) के रूप में माना जाता है।
यह आलेख केवल ग्राफ़ एम्बेडिंग की सख्त परिभाषा से संबंधित है। [[ग्राफ ड्राइंग]] और क्रॉसिंग नंबर (ग्राफ सिद्धांत) लेखों में कमजोर परिभाषा पर चर्चा की गई है।
 
कुछ लेखक किनारों के लिए गैर-प्रतिच्छेदन स्थिति को छोड़कर ग्राफ एम्बेडिंग की परिभाषा के अशक्त संस्करण को परिभाषित करते हैं। ऐसे संदर्भों में सख्त परिभाषा को नॉन-क्रॉसिंग ग्राफ एम्बेडिंग के रूप में वर्णित किया गया है।<ref>{{citation|first1=Naoki|last1=Katoh|first2=Shin-ichi|last2=Tanigawa|title=Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings|publisher=Springer-Verlag|series=[[Lecture Notes in Computer Science]]|volume=4598|year=2007|pages=243–253|doi=10.1007/978-3-540-73545-8_25|chapter=Enumerating Constrained Non-crossing Geometric Spanning Trees|isbn=978-3-540-73544-1|citeseerx=10.1.1.483.874}}.</ref>
 
यह आलेख केवल ग्राफ़ एम्बेडिंग की सख्त परिभाषा से संबंधित है। [[ग्राफ ड्राइंग]] और क्रॉसिंग नंबर (ग्राफ सिद्धांत) लेखों में अशक्त परिभाषा पर चर्चा की गई है।


==शब्दावली==
==शब्दावली==
एक ग्राफ का <math>G</math> एक बंद सतह पर जड़ा हुआ है <math>\Sigma</math>, से जुड़े बिंदुओं और चापों के मिलन का पूरक
यदि एक ग्राफ <math>G</math> एक बंद सतह <math>\Sigma</math> पर एम्बेडेड है, तो <math>G</math> के शीर्षों और किनारों से जुड़े बिंदुओं और चापों के मिलन का पूरक क्षेत्रों (या चेहरों) का एक वर्ग है।<ref name="gt01">{{citation|last1=Gross|first1=Jonathan|last2=Tucker|first2=Thomas W.|authorlink2= Thomas W. Tucker| title=Topological Graph Theory|publisher=Dover Publications|year=2001|isbn=978-0-486-41741-7}}.</ref> 2-सेल एम्बेडिंग, सेल्युलर एम्बेडिंग या मैप एक एम्बेडिंग है जिसमें प्रत्येक चेहरा एक खुली डिस्क के होमियोमॉर्फिक होता है।<ref>{{citation|last1=Lando|first1=Sergei K.|last2=Zvonkin|first2=Alexander K.|title=Graphs on Surfaces and their Applications|publisher=Springer-Verlag|year=2004|isbn=978-3-540-00203-1}}.</ref> एक बंद 2-सेल एम्बेडिंग एक एम्बेडिंग है जिसमें प्रत्येक चेहरे का बंद होना एक बंद डिस्क के होमियोमॉर्फिक है।
के शीर्ष और किनारे <math>G</math> क्षेत्रों (या फलक (ग्राफ़ सिद्धांत)) का एक परिवार है।<ref name="gt01">{{citation|last1=Gross|first1=Jonathan|last2=Tucker|first2=Thomas W.|authorlink2= Thomas W. Tucker| title=Topological Graph Theory|publisher=Dover Publications|year=2001|isbn=978-0-486-41741-7}}.</ref> 2-सेल एम्बेडिंग, सेल्युलर एम्बेडिंग या मैप एक एम्बेडिंग है जिसमें प्रत्येक चेहरा एक खुली डिस्क के लिए होमियोमॉर्फिक होता है।<ref>{{citation|last1=Lando|first1=Sergei K.|last2=Zvonkin|first2=Alexander K.|title=Graphs on Surfaces and their Applications|publisher=Springer-Verlag|year=2004|isbn=978-3-540-00203-1}}.</ref> एक बंद 2-सेल एम्बेडिंग एक एम्बेडिंग है जिसमें प्रत्येक चेहरे का बंद होना एक बंद डिस्क के होमियोमॉर्फिक है।


ग्राफ़ का जीनस (असतत गणित) न्यूनतम पूर्णांक है <math>n</math> इस तरह कि ग्राफ़ को जीनस (गणित) की सतह में एम्बेड किया जा सकता है <math>n</math>. विशेष रूप से, एक समतलीय ग्राफ़ में जीनस होता है <math>0</math>, क्योंकि इसे स्वयं-क्रॉसिंग के बिना एक गोले पर खींचा जा सकता है। एक ग्राफ जिसे [[ टोरस्र्स |टोरस्र्स]] पर एम्बेड किया जा सकता है उसे [[टोरॉयडल ग्राफ]] कहा जाता है।
ग्राफ़ का जीनस न्यूनतम पूर्णांक <math>n</math> होता है, जिससे ग्राफ़ को जीनस <math>n</math> की सतह में एम्बेड किया जा सके। विशेष रूप से, एक समतलीय ग्राफ़ में जीनस <math>0</math> होता है, क्योंकि इसे स्वयं-क्रॉसिंग के बिना एक गोले पर खींचा जा सकता है। एक ग्राफ जिसे टोरस पर एम्बेड किया जा सकता है उसे टॉरॉयडल ग्राफ कहा जाता है।


ग्राफ़ (असतत गणित) का गैर-उन्मुख जीनस न्यूनतम पूर्णांक है <math>n</math> ऐसा कि ग्राफ़ को (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में एम्बेड किया जा सकता है <math>n</math>.<ref name="gt01"/>
ग्राफ़ (असतत गणित) का गैर-उन्मुख जीनस न्यूनतम पूर्णांक है <math>n</math> ऐसा कि ग्राफ़ को (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में एम्बेड किया जा सकता है <math>n</math>.<ref name="gt01"/>
Line 41: Line 42:
ग्राफ़ का यूलर जीनस न्यूनतम पूर्णांक है <math>n</math> ऐसा कि ग्राफ़ को (ओरिएंटेबल) जीनस की ओरिएंटेबल सतह में एम्बेड किया जा सकता है <math>n/2</math> या (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में <math>n</math>. एक ग्राफ उन्मुख रूप से सरल होता है यदि इसका यूलर जीनस इसके गैर-उन्मुख जीनस से छोटा है।
ग्राफ़ का यूलर जीनस न्यूनतम पूर्णांक है <math>n</math> ऐसा कि ग्राफ़ को (ओरिएंटेबल) जीनस की ओरिएंटेबल सतह में एम्बेड किया जा सकता है <math>n/2</math> या (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में <math>n</math>. एक ग्राफ उन्मुख रूप से सरल होता है यदि इसका यूलर जीनस इसके गैर-उन्मुख जीनस से छोटा है।


ग्राफ़ (असतत गणित) का अधिकतम जीनस अधिकतम पूर्णांक है <math>n</math> ऐसा कि ग्राफ हो सकता है <math>2</math>-सेल जीनस (गणित) की एक उन्मुख सतह में एम्बेडेड है <math>n</math>.
किसी ग्राफ़ का अधिकतम जीनस अधिकतम पूर्णांक <math>n</math> होता है, जिससे ग्राफ़ जीनस <math>n</math> की ओरिएंटेबल सतह में <math>2</math>-सेल एम्बेडेड हो सकता है।


==कॉम्बिनेटोरियल एम्बेडिंग==
==कॉम्बिनेटोरियल एम्बेडिंग==
{{main|Rotation system}}
{{main|घूर्णन प्रणाली}}
एक एम्बेडेड ग्राफ़ एक ही शीर्ष पर आपतित किनारों के [[चक्रीय क्रम]] को विशिष्ट रूप से परिभाषित करता है। इन सभी चक्रीय आदेशों के समुच्चय को घूर्णन प्रणाली कहा जाता है। समान [[ रोटेशन प्रणाली |रोटेशन प्रणाली]] वाले एंबेडिंग्स को समतुल्य माना जाता है और एंबेडिंग्स के संबंधित समतुल्य वर्ग को कॉम्बिनेटोरियल एंबेडिंग कहा जाता है (टोपोलॉजिकल एंबेडिंग शब्द के विपरीत, जो बिंदुओं और वक्रों के संदर्भ में पिछली परिभाषा को संदर्भित करता है)। कभी-कभी, रोटेशन सिस्टम को ही कॉम्बिनेटोरियल एम्बेडिंग कहा जाता है।<ref>{{citation|first1=Petra|last1=Mutzel|author1-link=Petra Mutzel|first2=René|last2=Weiskircher|title=Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings|year=2000|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=1858|pages=95–104|doi=10.1007/3-540-44968-X_10|chapter=Computing Optimal Embeddings for Planar Graphs|isbn=978-3-540-67787-1}}.</ref><ref>{{citation|last=Didjev|first=Hristo N.|contribution=On drawing a graph convexly in the plane|title=Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=1995|volume=894|pages=76–83|doi=10.1007/3-540-58950-3_358|title-link=International Symposium on Graph Drawing|isbn=978-3-540-58950-1|doi-access=free}}.</ref><ref>{{citation|first1=Christian|last1=Duncan|first2=Michael T.|last2=Goodrich|author2-link=Michael T. Goodrich|first3=Stephen|last3=Kobourov|title=Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=2010|pages=45–56|doi=10.1007/978-3-642-11805-0_7|volume=5849|chapter=Planar Drawings of Higher-Genus Graphs|isbn=978-3-642-11804-3|title-link=International Symposium on Graph Drawing|arxiv=0908.1608}}.</ref>
एक एम्बेडेड ग्राफ़ एक ही शीर्ष पर आपतित किनारों के [[चक्रीय क्रम]] को विशिष्ट रूप से परिभाषित करता है। इन सभी चक्रीय आदेशों के समुच्चय को घूर्णन प्रणाली कहा जाता है। समान [[ रोटेशन प्रणाली |घूर्णन प्रणाली]] वाले एंबेडिंग्स को समतुल्य माना जाता है और एंबेडिंग्स के संबंधित समतुल्य वर्ग को कॉम्बिनेटोरियल एंबेडिंग कहा जाता है (टोपोलॉजिकल एंबेडिंग शब्द के विपरीत, जो बिंदुओं और वक्रों के संदर्भ में पिछली परिभाषा को संदर्भित करता है)। कभी-कभी, घूर्णन प्रणाली को ही कॉम्बिनेटोरियल एम्बेडिंग कहा जाता है।<ref>{{citation|first1=Petra|last1=Mutzel|author1-link=Petra Mutzel|first2=René|last2=Weiskircher|title=Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings|year=2000|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=1858|pages=95–104|doi=10.1007/3-540-44968-X_10|chapter=Computing Optimal Embeddings for Planar Graphs|isbn=978-3-540-67787-1}}.</ref><ref>{{citation|last=Didjev|first=Hristo N.|contribution=On drawing a graph convexly in the plane|title=Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=1995|volume=894|pages=76–83|doi=10.1007/3-540-58950-3_358|title-link=International Symposium on Graph Drawing|isbn=978-3-540-58950-1|doi-access=free}}.</ref><ref>{{citation|first1=Christian|last1=Duncan|first2=Michael T.|last2=Goodrich|author2-link=Michael T. Goodrich|first3=Stephen|last3=Kobourov|title=Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=2010|pages=45–56|doi=10.1007/978-3-642-11805-0_7|volume=5849|chapter=Planar Drawings of Higher-Genus Graphs|isbn=978-3-642-11804-3|title-link=International Symposium on Graph Drawing|arxiv=0908.1608}}.</ref>
एक एम्बेडेड ग्राफ़ किनारों के प्राकृतिक चक्रीय क्रम को भी परिभाषित करता है जो एम्बेडिंग के चेहरों की सीमाओं का गठन करता है। हालाँकि इन फेस-आधारित आदेशों को संभालना कम सरल है, क्योंकि कुछ मामलों में कुछ किनारों को फेस सीमा के साथ दो बार पार किया जा सकता है। उदाहरण के लिए, यह हमेशा पेड़ों के एम्बेडिंग के मामले में होता है, जिनका एक ही चेहरा होता है। इस संयुक्त उपद्रव को दूर करने के लिए, कोई यह मान सकता है कि प्रत्येक किनारे को लंबाई में दो आधे-किनारों, या किनारों में विभाजित किया गया है। इस परिपाटी के तहत सभी फेस सीमा ट्रैवर्सल में प्रत्येक आधे किनारे को केवल एक बार पार किया जाता है और एक ही किनारे के दो आधे किनारों को हमेशा विपरीत दिशाओं में पार किया जाता है।


सेलुलर एम्बेडिंग के लिए अन्य समकक्ष प्रतिनिधित्व में [[रिबन ग्राफ]], एक एम्बेडेड ग्राफ के कोने और किनारों के लिए टोपोलॉजिकल डिस्क को एक साथ जोड़कर गठित एक टोपोलॉजिकल स्पेस, [[ग्राफ़-एन्कोडेड मानचित्र]] मानचित्र, प्रत्येक किनारे के लिए चार कोने के साथ एक किनारे-रंगीन [[ घन ग्राफ |घन ग्राफ]] शामिल है। एम्बेडेड ग्राफ़.
एक एम्बेडेड ग्राफ़ किनारों के प्राकृतिक चक्रीय क्रम को भी परिभाषित करता है जो एम्बेडिंग के चेहरों की सीमाओं का गठन करता है। चूँकि इन फेस-आधारित आदेशों को संभालना कम सरल है, क्योंकि कुछ स्थिति में कुछ किनारों को फेस सीमा के साथ दो बार पार किया जा सकता है। उदाहरण के लिए, यह सदैव पेड़ों के एम्बेडिंग के स्थिति में होता है, जिनका एक ही चेहरा होता है। इस संयुक्त उपद्रव को दूर करने के लिए, कोई यह मान सकता है कि प्रत्येक किनारे को लंबाई में दो आधे-किनारों, या किनारों में विभाजित किया गया है। इस परिपाटी के तहत सभी फेस सीमा ट्रैवर्सल में प्रत्येक आधे किनारे को केवल एक बार पार किया जाता है और एक ही किनारे के दो आधे किनारों को सदैव विपरीत दिशाओं में पार किया जाता है।
 
सेलुलर एम्बेडिंग के लिए अन्य समतुल्य अभ्यावेदन में रिबन ग्राफ, एक एम्बेडेड ग्राफ़ के शीर्षों और किनारों के लिए टोपोलॉजिकल डिस्क को एक साथ जोड़कर बनाई गई एक टोपोलॉजिकल स्पेस और ग्राफ़-एन्कोडेड मानचित्र एक किनारे-रंगीन क्यूबिक ग्राफ़ सम्मिलित है जिसमें एम्बेडेड ग्राफ के प्रत्येक किनारे के लिए चार कोने होते हैं।


==कम्प्यूटेशनल जटिलता==
==कम्प्यूटेशनल जटिलता==


ग्राफ़ जीनस को खोजने की समस्या [[ एनपी कठिन |एनपी कठिन]] है (यह निर्धारित करने की समस्या कि क्या कोई <math>n</math>-वर्टेक्स ग्राफ में जीनस है <math>g</math> एनपी-पूर्ण है)।<ref>{{Citation | last1=Thomassen | first1=Carsten | authorlink = Carsten Thomassen (mathematician) | title=The graph genus problem is NP-complete | year=1989 | journal=Journal of Algorithms | volume=10 | issue = 4 | pages=568–576 | doi = 10.1016/0196-6774(89)90006-0}}</ref>
ग्राफ़ जीनस खोजने की समस्या एनपी-हार्ड है (यह निर्धारित करने की समस्या कि <math>n</math>-वर्टेक्स ग्राफ़ में जीनस <math>g</math> है या नहीं, एनपी-पूर्ण है)।<ref>{{Citation | last1=Thomassen | first1=Carsten | authorlink = Carsten Thomassen (mathematician) | title=The graph genus problem is NP-complete | year=1989 | journal=Journal of Algorithms | volume=10 | issue = 4 | pages=568–576 | doi = 10.1016/0196-6774(89)90006-0}}</ref>
साथ ही, ग्राफ़ जीनस समस्या [[फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी]] है। फिक्स्ड-पैरामीटर ट्रैक्टेबल, यानी, बहुपद समय एल्गोरिदम यह जांचने के लिए जाने जाते हैं कि ग्राफ़ को किसी दिए गए निश्चित जीनस की सतह में एम्बेड किया जा सकता है या नहीं और साथ ही एम्बेडिंग भी ढूंढी जा सकती है। .
 
एक ही समय में ग्राफ जीनस समस्या निश्चित-पैरामीटर ट्रैक्टेबल है, अथार्त , बहुपद समय एल्गोरिदम को यह जांचने के लिए जाना जाता है कि क्या एक ग्राफ को किसी दिए गए निश्चित जीनस की सतह में एम्बेड किया जा सकता है और साथ ही एम्बेडिंग भी खोजी जा सकती है।
 
इस संबंध में पहली सफलता 1979 में हुई, जब समय जटिलता ''O''(''n<sup>O</sup>''<sup>(''g'')</sup>) के एल्गोरिदम स्वतंत्र रूप से कंप्यूटिंग के सिद्धांत पर वार्षिक एसीएम संगोष्ठी में प्रस्तुत किए गए थे: आई. फिलोटी और गैरी मिलर (कंप्यूटर वैज्ञानिक)|जी.एल. मिलर और दूसरा [[जॉन रीफ़]] द्वारा। उनके दृष्टिकोण बिल्कुल अलग थे, लेकिन कार्यक्रम समिति के सुझाव पर उन्होंने एक संयुक्त पत्र प्रस्तुत किया।<ref>{{citation|first1=I. S.|last1=Filotti|author2-link=Gary Miller (computer scientist)|first2=Gary L.|last2=Miller|first3=John|last3=Reif|author3-link=John Reif |title=Proc. 11th Annu. ACM Symposium on Theory of Computing|year=1979|pages=27–37|doi=10.1145/800135.804395|chapter=On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)|title-link=Symposium on Theory of Computing|doi-access=free}}.</ref> चूँकि [[वेंडी मायरवॉल्ड]] और [[विलियम लॉरेंस कोके]] ने 2011 में सिद्ध किया कि फिलोटी, मिलर और रीफ द्वारा दिया गया एल्गोरिदम गलत था।<ref>{{cite journal|last1=Myrvold|first1=Wendy|author1-link=Wendy Myrvold|last2=Kocay|first2=William|author2-link=William Lawrence Kocay|title=ग्राफ़ एम्बेडिंग एल्गोरिदम में त्रुटियाँ|journal=Journal of Computer and System Sciences|date=March 1, 2011|volume=2|issue=77|page=430–438|doi=10.1016/j.jcss.2010.06.002|doi-access=free}}</ref>
 
1999 में यह बताया गया कि फिक्स्ड-जीनस स्थिति को ग्राफ आकार में [[रैखिक समय]] और जीनस में [[दोहरा घातीय कार्य]] में हल किया जा सकता है।<ref>{{Citation | last1=Mohar | first1=Bojan | authorlink = Bojan Mohar | title=A linear time algorithm for embedding graphs in an arbitrary surface | year=1999 | journal=[[SIAM Journal on Discrete Mathematics]] | volume=12 | issue=1 | pages=6–26 | doi = 10.1137/S089548019529248X| citeseerx=10.1.1.97.9588 }}</ref>


इस संबंध में पहली सफलता 1979 में हुई, जब समय जटिलता के एल्गोरिदम
पर<sup>ओ(जी)</sup>) को स्वतंत्र रूप से कंप्यूटिंग के सिद्धांत पर वार्षिक एसीएम संगोष्ठी में प्रस्तुत किया गया था: आई. फिलोटी और गैरी मिलर (कंप्यूटर वैज्ञानिक)|जी.एल. मिलर और दूसरा [[जॉन रीफ़]] द्वारा। उनके दृष्टिकोण बिल्कुल अलग थे, लेकिन कार्यक्रम समिति के सुझाव पर उन्होंने एक संयुक्त पत्र प्रस्तुत किया।<ref>{{citation|first1=I. S.|last1=Filotti|author2-link=Gary Miller (computer scientist)|first2=Gary L.|last2=Miller|first3=John|last3=Reif|author3-link=John Reif |title=Proc. 11th Annu. ACM Symposium on Theory of Computing|year=1979|pages=27–37|doi=10.1145/800135.804395|chapter=On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)|title-link=Symposium on Theory of Computing|doi-access=free}}.</ref> हालाँकि, [[वेंडी मायरवॉल्ड]] और [[विलियम लॉरेंस कोके]] ने 2011 में साबित किया कि फिलोटी, मिलर और रीफ द्वारा दिया गया एल्गोरिदम गलत था।<ref>{{cite journal|last1=Myrvold|first1=Wendy|author1-link=Wendy Myrvold|last2=Kocay|first2=William|author2-link=William Lawrence Kocay|title=ग्राफ़ एम्बेडिंग एल्गोरिदम में त्रुटियाँ|journal=Journal of Computer and System Sciences|date=March 1, 2011|volume=2|issue=77|page=430–438|doi=10.1016/j.jcss.2010.06.002|doi-access=free}}</ref>
1999 में यह बताया गया कि फिक्स्ड-जीनस मामले को ग्राफ आकार में [[रैखिक समय]] और जीनस में [[दोहरा घातीय कार्य]] में हल किया जा सकता है।<ref>{{Citation | last1=Mohar | first1=Bojan | authorlink = Bojan Mohar | title=A linear time algorithm for embedding graphs in an arbitrary surface | year=1999 | journal=[[SIAM Journal on Discrete Mathematics]] | volume=12 | issue=1 | pages=6–26 | doi = 10.1137/S089548019529248X| citeseerx=10.1.1.97.9588 }}</ref>




Line 63: Line 67:
यह ज्ञात है कि किसी भी परिमित ग्राफ को त्रि-आयामी स्थान में एम्बेड किया जा सकता है।<ref name="3d-gd"/>
यह ज्ञात है कि किसी भी परिमित ग्राफ को त्रि-आयामी स्थान में एम्बेड किया जा सकता है।<ref name="3d-gd"/>


ऐसा करने का एक तरीका यह है कि बिंदुओं को अंतरिक्ष में किसी भी रेखा पर रखा जाए और किनारों को वक्र के रूप में खींचा जाए, जिनमें से प्रत्येक एक अलग आधे तल में स्थित हो, सभी आधे तलों में वह रेखा उनकी सामान्य सीमा के रूप में हो। इस तरह की एम्बेडिंग जिसमें किनारों को आधे समतल पर खींचा जाता है, ग्राफ़ की [[ पुस्तक एम्बेडिंग |पुस्तक एम्बेडिंग]] कहलाती है। यह [[रूपक]] इस कल्पना से आता है कि प्रत्येक तल जहां एक किनारा खींचा गया है, एक किताब के एक पृष्ठ की तरह है। यह देखा गया कि वास्तव में एक ही पृष्ठ में कई किनारे बनाये जा सकते हैं; ग्राफ़ की पुस्तक की मोटाई ऐसे चित्र के लिए आवश्यक आधे तलों की न्यूनतम संख्या है।
ऐसा करने का एक विधि यह है कि बिंदुओं को स्थान में किसी भी रेखा पर रखा जाए और किनारों को वक्र के रूप में खींचा जाए, जिनमें से प्रत्येक एक अलग आधे तल में स्थित हो, सभी आधे तलों में वह रेखा उनकी सामान्य सीमा के रूप में हो सकता है इस तरह की एम्बेडिंग जिसमें किनारों को आधे समतल पर खींचा जाता है, ग्राफ़ की [[ पुस्तक एम्बेडिंग |पुस्तक एम्बेडिंग]] कहलाती है। यह [[रूपक]] इस कल्पना से आता है कि प्रत्येक तल जहां एक किनारा खींचा गया है, एक किताब के एक पृष्ठ की तरह है। यह देखा गया कि वास्तव में एक ही पृष्ठ में कई किनारे बनाये जा सकते हैं; ग्राफ़ की पुस्तक की मोटाई ऐसे चित्र के लिए आवश्यक आधे तलों की न्यूनतम संख्या है।


वैकल्पिक रूप से, किसी भी परिमित ग्राफ को उसके शीर्षों को [[सामान्य स्थिति]] में रखकर तीन आयामों में सीधी रेखा के किनारों के साथ बिना किसी क्रॉसिंग के खींचा जा सकता है ताकि कोई भी चार समतलीय न हो। उदाहरण के लिए, इसे ith शीर्ष को बिंदु (i,i) पर रखकर प्राप्त किया जा सकता है<sup>2</sup>,i<sup>3</sup>) [[क्षण वक्र]] का।
वैकल्पिक रूप से, किसी भी परिमित ग्राफ को उसके शीर्षों को सामान्य स्थिति में रखकर तीन आयामों में सीधी रेखा के किनारों के साथ बिना किसी क्रॉसिंग के खींचा जा सकता है जिससे कोई भी चार समतलीय न हो। उदाहरण के लिए, इसे क्षण वक्र के बिंदु (''i'',''i''<sup>2</sup>,''i''<sup>3</sup>) पर ith शीर्ष रखकर प्राप्त किया जा सकता है।


एक ग्राफ़ को त्रि-आयामी स्थान में एम्बेड करना जिसमें कोई भी दो चक्र टोपोलॉजिकल रूप से जुड़े हुए नहीं हैं, लिंकलेस एम्बेडिंग कहलाता है। एक ग्राफ़ में [[लिंक रहित एम्बेडिंग]] होती है यदि और केवल तभी जब इसमें [[पीटरसन परिवार]] के सात ग्राफ़ों में से एक नाबालिग (ग्राफ़ सिद्धांत) के रूप में न हो।
एक ग्राफ़ को त्रि-आयामी स्थान में एम्बेड करना जिसमें कोई भी दो चक्र टोपोलॉजिकल रूप से जुड़े हुए नहीं हैं, लिंकलेस एम्बेडिंग कहलाता है। एक ग्राफ़ में [[लिंक रहित एम्बेडिंग]] होती है यदि और केवल तभी जब इसमें [[पीटरसन परिवार|पीटरसन]] वर्ग के सात ग्राफ़ों में से एक नाबालिग (ग्राफ़ सिद्धांत) के रूप में न हो।


==गैलरी==
==गैलरी==
Line 84: Line 88:
* [[दोगुनी कनेक्टेड एज सूची]], समतल (ज्यामिति) में ग्राफ [[एम्बेडिंग]] का प्रतिनिधित्व करने के लिए एक डेटा संरचना
* [[दोगुनी कनेक्टेड एज सूची]], समतल (ज्यामिति) में ग्राफ [[एम्बेडिंग]] का प्रतिनिधित्व करने के लिए एक डेटा संरचना
* [[नियमित मानचित्र (ग्राफ़ सिद्धांत)]]
* [[नियमित मानचित्र (ग्राफ़ सिद्धांत)]]
* फ़ेरी का प्रमेय, जो कहता है कि एक समतलीय ग्राफ़ का एक सीधी रेखा समतलीय एम्बेडिंग हमेशा संभव है।
* फ़ेरी का प्रमेय, जो कहता है कि एक समतलीय ग्राफ़ का एक सीधी रेखा समतलीय एम्बेडिंग सदैव संभव है।
* [[त्रिकोणासन (ज्यामिति)]]
* [[त्रिकोणासन (ज्यामिति)]]


==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}
[[Category: टोपोलॉजिकल ग्राफ सिद्धांत]] [[Category: ग्राफ़ एल्गोरिदम]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Created On 01/07/2023]]
[[Category:Created On 01/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:ग्राफ़ एल्गोरिदम]]
[[Category:टोपोलॉजिकल ग्राफ सिद्धांत]]

Latest revision as of 18:12, 12 July 2023

हेवुड ग्राफ़ और संबंधित मानचित्र टोरस में सन्निहित है।


टोपोलॉजिकल ग्राफ सिद्धांत में, एक सतह पर ग्राफ का एक एम्बेडिंग (इम्बेडिंग भी लिखा जाता है) पर का एक प्रतिनिधित्व है जिसमें के बिंदु शीर्षों और सरल चापों से जुड़े होते हैं ([0,1 की होमियोमोर्फिक छवियां) ]) किनारों से इस प्रकार जुड़े हुए हैं कि:

  • एक किनारे से जुड़े चाप के अंतिम बिंदु के अंतिम शीर्ष से जुड़े बिंदु हैं।
  • किसी भी चाप में अन्य शीर्षों से जुड़े बिंदु सम्मिलित नहीं हैं,
  • दो चाप कभी भी ऐसे बिंदु पर प्रतिच्छेद नहीं करते जो किसी भी चाप का आंतरिक भाग हो।

यहां एक सतह -मैनिफोल्ड से जुड़ी एक कॉम्पैक्ट है।

अनौपचारिक रूप से, किसी ग्राफ़ को किसी सतह पर एम्बेड करना सतह पर ग्राफ़ को इस तरह से चित्रित करना है कि इसके किनारे केवल अपने अंतिम बिंदुओं पर ही प्रतिच्छेद कर सकता है। यह सर्वविदित है कि किसी भी परिमित ग्राफ को 3-आयामी यूक्लिडियन स्पेस में एम्बेड किया जा सकता है।[1] एक समतल ग्राफ वह है जिसे 2-आयामी यूक्लिडियन स्पेस में एम्बेड किया जा सकता है।

अक्सर, एक एम्बेडिंग को वर्णित प्रकार के अभ्यावेदन के समतुल्य वर्ग ( के होमोमोर्फिज्म के तहत) के रूप में माना जाता है।

कुछ लेखक किनारों के लिए गैर-प्रतिच्छेदन स्थिति को छोड़कर ग्राफ एम्बेडिंग की परिभाषा के अशक्त संस्करण को परिभाषित करते हैं। ऐसे संदर्भों में सख्त परिभाषा को नॉन-क्रॉसिंग ग्राफ एम्बेडिंग के रूप में वर्णित किया गया है।[2]

यह आलेख केवल ग्राफ़ एम्बेडिंग की सख्त परिभाषा से संबंधित है। ग्राफ ड्राइंग और क्रॉसिंग नंबर (ग्राफ सिद्धांत) लेखों में अशक्त परिभाषा पर चर्चा की गई है।

शब्दावली

यदि एक ग्राफ एक बंद सतह पर एम्बेडेड है, तो के शीर्षों और किनारों से जुड़े बिंदुओं और चापों के मिलन का पूरक क्षेत्रों (या चेहरों) का एक वर्ग है।[3] 2-सेल एम्बेडिंग, सेल्युलर एम्बेडिंग या मैप एक एम्बेडिंग है जिसमें प्रत्येक चेहरा एक खुली डिस्क के होमियोमॉर्फिक होता है।[4] एक बंद 2-सेल एम्बेडिंग एक एम्बेडिंग है जिसमें प्रत्येक चेहरे का बंद होना एक बंद डिस्क के होमियोमॉर्फिक है।

ग्राफ़ का जीनस न्यूनतम पूर्णांक होता है, जिससे ग्राफ़ को जीनस की सतह में एम्बेड किया जा सके। विशेष रूप से, एक समतलीय ग्राफ़ में जीनस होता है, क्योंकि इसे स्वयं-क्रॉसिंग के बिना एक गोले पर खींचा जा सकता है। एक ग्राफ जिसे टोरस पर एम्बेड किया जा सकता है उसे टॉरॉयडल ग्राफ कहा जाता है।

ग्राफ़ (असतत गणित) का गैर-उन्मुख जीनस न्यूनतम पूर्णांक है ऐसा कि ग्राफ़ को (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में एम्बेड किया जा सकता है .[3]

ग्राफ़ का यूलर जीनस न्यूनतम पूर्णांक है ऐसा कि ग्राफ़ को (ओरिएंटेबल) जीनस की ओरिएंटेबल सतह में एम्बेड किया जा सकता है या (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में . एक ग्राफ उन्मुख रूप से सरल होता है यदि इसका यूलर जीनस इसके गैर-उन्मुख जीनस से छोटा है।

किसी ग्राफ़ का अधिकतम जीनस अधिकतम पूर्णांक होता है, जिससे ग्राफ़ जीनस की ओरिएंटेबल सतह में -सेल एम्बेडेड हो सकता है।

कॉम्बिनेटोरियल एम्बेडिंग

Main article: घूर्णन प्रणाली

एक एम्बेडेड ग्राफ़ एक ही शीर्ष पर आपतित किनारों के चक्रीय क्रम को विशिष्ट रूप से परिभाषित करता है। इन सभी चक्रीय आदेशों के समुच्चय को घूर्णन प्रणाली कहा जाता है। समान घूर्णन प्रणाली वाले एंबेडिंग्स को समतुल्य माना जाता है और एंबेडिंग्स के संबंधित समतुल्य वर्ग को कॉम्बिनेटोरियल एंबेडिंग कहा जाता है (टोपोलॉजिकल एंबेडिंग शब्द के विपरीत, जो बिंदुओं और वक्रों के संदर्भ में पिछली परिभाषा को संदर्भित करता है)। कभी-कभी, घूर्णन प्रणाली को ही कॉम्बिनेटोरियल एम्बेडिंग कहा जाता है।[5][6][7]

एक एम्बेडेड ग्राफ़ किनारों के प्राकृतिक चक्रीय क्रम को भी परिभाषित करता है जो एम्बेडिंग के चेहरों की सीमाओं का गठन करता है। चूँकि इन फेस-आधारित आदेशों को संभालना कम सरल है, क्योंकि कुछ स्थिति में कुछ किनारों को फेस सीमा के साथ दो बार पार किया जा सकता है। उदाहरण के लिए, यह सदैव पेड़ों के एम्बेडिंग के स्थिति में होता है, जिनका एक ही चेहरा होता है। इस संयुक्त उपद्रव को दूर करने के लिए, कोई यह मान सकता है कि प्रत्येक किनारे को लंबाई में दो आधे-किनारों, या किनारों में विभाजित किया गया है। इस परिपाटी के तहत सभी फेस सीमा ट्रैवर्सल में प्रत्येक आधे किनारे को केवल एक बार पार किया जाता है और एक ही किनारे के दो आधे किनारों को सदैव विपरीत दिशाओं में पार किया जाता है।

सेलुलर एम्बेडिंग के लिए अन्य समतुल्य अभ्यावेदन में रिबन ग्राफ, एक एम्बेडेड ग्राफ़ के शीर्षों और किनारों के लिए टोपोलॉजिकल डिस्क को एक साथ जोड़कर बनाई गई एक टोपोलॉजिकल स्पेस और ग्राफ़-एन्कोडेड मानचित्र एक किनारे-रंगीन क्यूबिक ग्राफ़ सम्मिलित है जिसमें एम्बेडेड ग्राफ के प्रत्येक किनारे के लिए चार कोने होते हैं।

कम्प्यूटेशनल जटिलता

ग्राफ़ जीनस खोजने की समस्या एनपी-हार्ड है (यह निर्धारित करने की समस्या कि -वर्टेक्स ग्राफ़ में जीनस है या नहीं, एनपी-पूर्ण है)।[8]

एक ही समय में ग्राफ जीनस समस्या निश्चित-पैरामीटर ट्रैक्टेबल है, अथार्त , बहुपद समय एल्गोरिदम को यह जांचने के लिए जाना जाता है कि क्या एक ग्राफ को किसी दिए गए निश्चित जीनस की सतह में एम्बेड किया जा सकता है और साथ ही एम्बेडिंग भी खोजी जा सकती है।

इस संबंध में पहली सफलता 1979 में हुई, जब समय जटिलता O(nO(g)) के एल्गोरिदम स्वतंत्र रूप से कंप्यूटिंग के सिद्धांत पर वार्षिक एसीएम संगोष्ठी में प्रस्तुत किए गए थे: आई. फिलोटी और गैरी मिलर (कंप्यूटर वैज्ञानिक)|जी.एल. मिलर और दूसरा जॉन रीफ़ द्वारा। उनके दृष्टिकोण बिल्कुल अलग थे, लेकिन कार्यक्रम समिति के सुझाव पर उन्होंने एक संयुक्त पत्र प्रस्तुत किया।[9] चूँकि वेंडी मायरवॉल्ड और विलियम लॉरेंस कोके ने 2011 में सिद्ध किया कि फिलोटी, मिलर और रीफ द्वारा दिया गया एल्गोरिदम गलत था।[10]

1999 में यह बताया गया कि फिक्स्ड-जीनस स्थिति को ग्राफ आकार में रैखिक समय और जीनस में दोहरा घातीय कार्य में हल किया जा सकता है।[11]


उच्च-आयामी स्थानों में ग्राफ़ का एम्बेडिंग

यह ज्ञात है कि किसी भी परिमित ग्राफ को त्रि-आयामी स्थान में एम्बेड किया जा सकता है।[1]

ऐसा करने का एक विधि यह है कि बिंदुओं को स्थान में किसी भी रेखा पर रखा जाए और किनारों को वक्र के रूप में खींचा जाए, जिनमें से प्रत्येक एक अलग आधे तल में स्थित हो, सभी आधे तलों में वह रेखा उनकी सामान्य सीमा के रूप में हो सकता है इस तरह की एम्बेडिंग जिसमें किनारों को आधे समतल पर खींचा जाता है, ग्राफ़ की पुस्तक एम्बेडिंग कहलाती है। यह रूपक इस कल्पना से आता है कि प्रत्येक तल जहां एक किनारा खींचा गया है, एक किताब के एक पृष्ठ की तरह है। यह देखा गया कि वास्तव में एक ही पृष्ठ में कई किनारे बनाये जा सकते हैं; ग्राफ़ की पुस्तक की मोटाई ऐसे चित्र के लिए आवश्यक आधे तलों की न्यूनतम संख्या है।

वैकल्पिक रूप से, किसी भी परिमित ग्राफ को उसके शीर्षों को सामान्य स्थिति में रखकर तीन आयामों में सीधी रेखा के किनारों के साथ बिना किसी क्रॉसिंग के खींचा जा सकता है जिससे कोई भी चार समतलीय न हो। उदाहरण के लिए, इसे क्षण वक्र के बिंदु (i,i2,i3) पर ith शीर्ष रखकर प्राप्त किया जा सकता है।

एक ग्राफ़ को त्रि-आयामी स्थान में एम्बेड करना जिसमें कोई भी दो चक्र टोपोलॉजिकल रूप से जुड़े हुए नहीं हैं, लिंकलेस एम्बेडिंग कहलाता है। एक ग्राफ़ में लिंक रहित एम्बेडिंग होती है यदि और केवल तभी जब इसमें पीटरसन वर्ग के सात ग्राफ़ों में से एक नाबालिग (ग्राफ़ सिद्धांत) के रूप में न हो।

गैलरी

  • पीटरसन ग्राफ़ और संबंधित मानचित्र प्रक्षेप्य तल में सन्निहित है। वृत्त पर विपरीत बिंदुओं की पहचान गैर-उन्मुख जीनस 1 की एक बंद सतह के रूप में की जाती है।

    पीटरसन ग्राफ़ और संबंधित मानचित्र प्रक्षेप्य तल में सन्निहित है। वृत्त पर विपरीत बिंदुओं की पहचान गैर-उन्मुख जीनस 1 की एक बंद सतह के रूप में की जाती है।

  • पप्पस ग्राफ़ और संबंधित मानचित्र टोरस में सन्निहित है।

    पप्पस ग्राफ़ और संबंधित मानचित्र टोरस में सन्निहित है।

  • डिग्री 7 क्लेन ग्राफ और संबंधित मानचित्र जीनस 3 की एक उन्मुख सतह में एम्बेडेड है।

    डिग्री 7 क्लेन ग्राफ और संबंधित मानचित्र जीनस 3 की एक उन्मुख सतह में एम्बेडेड है।


यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 Cohen, Robert F.; Eades, Peter; Lin, Tao; Ruskey, Frank (1995), "Three-dimensional graph drawing", in Tamassia, Roberto; Tollis, Ioannis G. (eds.), Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science, vol. 894, Springer, pp. 1–11, doi:10.1007/3-540-58950-3_351, ISBN 978-3-540-58950-1.
  2. ↑ Katoh, Naoki; Tanigawa, Shin-ichi (2007), "Enumerating Constrained Non-crossing Geometric Spanning Trees", Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4598, Springer-Verlag, pp. 243–253, CiteSeerX 10.1.1.483.874, doi:10.1007/978-3-540-73545-8_25, ISBN 978-3-540-73544-1.
  3. ↑ 3.0 3.1 Gross, Jonathan; Tucker, Thomas W. (2001), Topological Graph Theory, Dover Publications, ISBN 978-0-486-41741-7.
  4. ↑ Lando, Sergei K.; Zvonkin, Alexander K. (2004), Graphs on Surfaces and their Applications, Springer-Verlag, ISBN 978-3-540-00203-1.
  5. ↑ Mutzel, Petra; Weiskircher, René (2000), "Computing Optimal Embeddings for Planar Graphs", Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1858, Springer-Verlag, pp. 95–104, doi:10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1.
  6. ↑ Didjev, Hristo N. (1995), "On drawing a graph convexly in the plane", Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science, vol. 894, Springer-Verlag, pp. 76–83, doi:10.1007/3-540-58950-3_358, ISBN 978-3-540-58950-1.
  7. ↑ Duncan, Christian; Goodrich, Michael T.; Kobourov, Stephen (2010), "Planar Drawings of Higher-Genus Graphs", Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 45–56, arXiv:0908.1608, doi:10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3.
  8. ↑ Thomassen, Carsten (1989), "The graph genus problem is NP-complete", Journal of Algorithms, 10 (4): 568–576, doi:10.1016/0196-6774(89)90006-0
  9. ↑ Filotti, I. S.; Miller, Gary L.; Reif, John (1979), "On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)", Proc. 11th Annu. ACM Symposium on Theory of Computing, pp. 27–37, doi:10.1145/800135.804395.
  10. ↑ Myrvold, Wendy; Kocay, William (March 1, 2011). "ग्राफ़ एम्बेडिंग एल्गोरिदम में त्रुटियाँ". Journal of Computer and System Sciences. 2 (77): 430–438. doi:10.1016/j.jcss.2010.06.002.
  11. ↑ Mohar, Bojan (1999), "A linear time algorithm for embedding graphs in an arbitrary surface", SIAM Journal on Discrete Mathematics, 12 (1): 6–26, CiteSeerX 10.1.1.97.9588, doi:10.1137/S089548019529248X
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ग्राफ_एम्बेडिंग&oldid=214566’