एक द्विपक्षीय ग्राफ में क्रॉसिंग की संख्या न्यूनतम

Question

निम्नलिखित कलन विधि समस्या, जबकि कुछ असंबंधित के लिए एक ग्राफ ड्राइंग घटित हुआ दिखाए गए कॉलम में। हम प्रत्येक कॉलम के भीतर नोड्स को पुनर्व्यवस्थित कैसे कर सकते हैं ताकि किनारे क्रॉसिंग की संख्या कम हो? मुझे पता है कि यह समस्या सामान्य ग्राफ (link) के लिए एनपी-हार्ड है, लेकिन क्या यह कुछ चाल है कि ग्राफ द्विपक्षीय है?

एक अनुवर्ती के रूप में, क्या वहाँ एक तीसरे स्तंभ डब्ल्यू है, जो केवल वी के किनारों है तो क्या होगा? या आगे?

Answer 1

कागज On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi उल्लेख Garey और जॉनसन द्वारा पार नंबर पर मूल पत्र भी साबित कर दिया कि कि धार क्रॉसिंग की संख्या को कम द्विपक्षीय ग्राफ के लिए एनपी कठिन है। वास्तव में, यह अभी भी एनपी कठिन है, भले ही आप एक स्तंभ के लिए इष्टतम आदेश बताया जाता है:

एक द्विपक्षीय ग्राफ को देखते हुए, एक 2-परत वाली ड्राइंग पर प्रथम नोड सेट वी में नोड्स रखने के होते हैं एक सीधी रेखा एल 1 और में नोड्स को समानांतर रेखा एल 2 पर दूसरा नोड सेट डब्ल्यू रखता है। को कम करने की समस्या 2-स्तरित ड्राइंग में आर्क के बीच क्रॉसिंग की संख्या पहले हैरी और श्वेनक द्वारा पेश की गई थी। एक तरफा क्रॉसिंग न्यूनतमकरण समस्या एल 1 में पर वी में नोड्स का ऑर्डर करने के लिए कहती है कि आर्क क्रॉसिंग की संख्या कम हो गई है (जबकि के आदेश को एल 2 पर डब्ल्यू में नोड दिए गए हैं और तय किए गए हैं)। समस्या का अनुप्रयोग वीएलएसआई लेआउट और पदानुक्रमित चित्रों में पाया जा सकता है।

हालांकि, दो तरफा और एक तरफा समस्याओं को क्रमशः गारे और जॉनसन और ईड्स और वर्माल्ड द्वारा एनपी-हार्ड दिखाया गया है।

Answer 2

पीटर डी रिवाज ने इंगित किया कि यह एनपी-हार्ड है, लेकिन फिर भी यदि आप कुछ अनुमान के साथ ठीक हैं तो आप निम्न समाधान के साथ जा सकते हैं।

मेरा प्रारंभिक विचार ग्राफ़ लेआउटिंग के लिए कुछ बल-आधारित एल्गोरिदम का उपयोग करना था, लेकिन यह लागू करने के लिए थोड़ा कठिन हो सकता है। लेकिन हे, यह अद्भुत कार्यक्रम graphviz.org है, जो आपके लिए पूरा काम कर सकता है।

graph G{ 
    {rank=same A B C D E} 
    {rank=same F G H K I J} 

    A -- F; 
    A -- G; 
    A -- K; 
    A -- I; 
    A -- H; 
    A -- J; 

    B -- G; 

    C -- G; 
    C -- J; 

    D -- K; 
    D -- I; 
} 

रन:: dot -Tpng yourgraph -o yourgraph.png

और मुक्त :-) के लिए ऐसा ही कुछ मिलता है: