Left-right planarity test
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಗಣಿತಶಾಸ್ತ್ರದ ಒಂದು ಶಾಖೆಯಾದ ಎಡ-ಬಲ ಪ್ಲ್ಯಾನಾರಿಟಿ ಟೆಸ್ಟ್ ಅಥವಾ ಡಿ ಫ್ರೆಯ್ಸಿಕ್ಸ್-ರೊಸೆನ್ಸ್ಟಿಲ್ ಪ್ಲ್ಯಾನಾರಿಟಿ ಮಾನದಂಡವು ಆಳ-ಮೊದಲ ಹುಡುಕಾಟ ಮರಗಳ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಆಧರಿಸಿದ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳ ಗುಣಲಕ್ಷಣವಾಗಿದೆ, ಇದನ್ನು ಪ್ಯಾಟ್ರಿಸ್ ಒಸೋನಾ ಡಿ ಮೆಂಡೆಜ್ ಅವರು ಪ್ರಕಟಿಸಿದರು ಮತ್ತು ರೇಖೀಯ ಸಮಯ ಪ್ಲ್ಯಾನಾರಿಟಿ ಪರೀಕ್ಷಾ ಕ್ರಮಾವಳಿಗಳನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲು ಬಳಸಿದರು. 2003ರ ಆರು ಪ್ಲ್ಯಾನಾರಿಟಿ ಪರೀಕ್ಷಾ ಕ್ರಮಾವಳಿಗಳ ಪ್ರಾಯೋಗಿಕ ಹೋಲಿಕೆಯಲ್ಲಿ, ಇದು ಪರೀಕ್ಷಿಸಿದ ಅತ್ಯಂತ ವೇಗದ ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ. ಟಿ-ಅಲೈಕ್ ಮತ್ತು ಟಿ-ವಿರುದ್ಧ ಅಂಚುಗಳು ಗ್ರಾಫ್ ಜಿ ಯ ಯಾವುದೇ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟಕ್ಕೆ, ಮೊದಲ ಬಾರಿಗೆ ಶೃಂಗವನ್ನು ಕಂಡುಹಿಡಿಯುವಾಗ ಎದುರಾಗುವ ಅಂಚುಗಳು ಜಿ ಯ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟ ಮರವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತವೆ. ಇದು ಟ್ರೆಮಾಕ್ಸ್ ಮರವಾಗಿದೆ, ಅಂದರೆ ಉಳಿದ ಅಂಚುಗಳು (ಕೋಟ್ರೀ) ಪ್ರತಿಯೊಂದೂ ಟಿ ಯಲ್ಲಿ ಪೂರ್ವಜ ಮತ್ತು ವಂಶಸ್ಥರಾಗಿ ಪರಸ್ಪರ ಸಂಬಂಧಿಸಿರುವ ಒಂದು ಜೋಡಿ ಶೃಂಗಗಳನ್ನು ಸಂಪರ್ಕಿಸುತ್ತವೆ. ಟಿ-ಅಲೈಕ್ ಮತ್ತು ಟಿ-ವಿರುದ್ಧ ಸಂಬಂಧಗಳು ಎಂದು ಕರೆಯಲ್ಪಡುವ ಕೋಟ್ರೀ ಅಂಚುಗಳ ಜೋಡಿಗಳ ನಡುವಿನ ಎರಡು ಸಂಬಂಧಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲು ಮೂರು ರೀತಿಯ ಮಾದರಿಗಳನ್ನು ಬಳಸಬಹುದು. ಈ ಕೆಳಗಿನ ಅಂಕಿಗಳಲ್ಲಿ, ಸರಳ ವೃತ್ತಾಕಾರದ ನೋಡ್ಗಳು ಶೃಂಗಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ, ಡಬಲ್ ಸರ್ಕಲ್ ನೋಡ್ಗಳು ಸಬ್ಟ್ರೀಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ, ತಿರುಚಿದ ಭಾಗಗಳು ಮರದ ಮಾರ್ಗಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ ಮತ್ತು ಬಾಗಿದ ಚಾಪಗಳು ಕೋಟ್ರೀ ಅಂಚುಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ. ಪ್ರತಿ ಮರದ ಮೂಲವನ್ನು ಚಿತ್ರದ ಕೆಳಭಾಗದಲ್ಲಿ ತೋರಿಸಲಾಗಿದೆ. ಮೊದಲ ಚಿತ್ರದಲ್ಲಿ, ಅಂಚುಗಳನ್ನು ಟಿ-ಅಲೈಕ್ ಎಂದು ಲೇಬಲ್ ಮಾಡಲಾಗಿದೆ, ಅಂದರೆ, ಮರದ ಮೂಲಕ್ಕೆ ಹತ್ತಿರವಿರುವ ಅಂತಿಮ ಬಿಂದುಗಳಲ್ಲಿ, ಅವು ಎರಡೂ ಪ್ರತಿ ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಮರದ ಒಂದೇ ಬದಿಯಲ್ಲಿರುತ್ತವೆ. ಮುಂದಿನ ಎರಡು ಅಂಕಿಗಳಲ್ಲಿ, ಒಂದೇ ಲೇಬಲ್ಗಳನ್ನು ಹೊಂದಿರುವ ಅಂಚುಗಳು ಟಿ-ವಿರುದ್ಧವಾಗಿರುತ್ತವೆ, ಅಂದರೆ ಅವು ಪ್ರತಿ ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಮರದ ವಿವಿಧ ಬದಿಗಳಲ್ಲಿರುತ್ತವೆ. ಗುಣಲಕ್ಷಣವು ಜಿ ಒಂದು ರೇಖಾಚಿತ್ರವಾಗಿರಲಿ ಮತ್ತು ಟಿ ಜಿ ಯ ಟ್ರೆಮಾಕ್ಸ್ ಮರವಾಗಿರಲಿ. ಜಿ ಯ ಕೋಟ್ರೀ ಅಂಚುಗಳನ್ನು ಎರಡು ವರ್ಗಗಳಾಗಿ ವಿಂಗಡಿಸಿದರೆ ಮಾತ್ರ ಗ್ರಾಫ್ ಜಿ ಸಮತಟ್ಟಾಗಿರುತ್ತದೆ, ಇದರಿಂದಾಗಿ ಯಾವುದೇ ಎರಡು ಅಂಚುಗಳು ಟಿ-ಸಮಾನವಾಗಿದ್ದರೆ ಒಂದೇ ವರ್ಗಕ್ಕೆ ಸೇರುತ್ತವೆ ಮತ್ತು ಯಾವುದೇ ಎರಡು ಅಂಚುಗಳು ಟಿ-ವಿರುದ್ಧವಾಗಿದ್ದರೆ ವಿಭಿನ್ನ ವರ್ಗಗಳಿಗೆ ಸೇರುತ್ತವೆ. ಈ ಗುಣಲಕ್ಷಣವು ತಕ್ಷಣವೇ (ಅದಕ್ಷ) ಸಮತೋಲಿತತೆಯ ಪರೀಕ್ಷೆಗೆ ಕಾರಣವಾಗುತ್ತದೆಃ ಎಲ್ಲಾ ಜೋಡಿ ಅಂಚುಗಳಿಗೆ ಅವು ಟಿ-ಸಮಾನ ಅಥವಾ ಟಿ-ವಿರುದ್ಧವಾಗಿವೆಯೇ ಎಂದು ನಿರ್ಧರಿಸಿ, ಟಿ-ಸಮಾನ ಅಂಚುಗಳ ಪ್ರತಿಯೊಂದು ಸಂಪರ್ಕಿತ ಘಟಕಕ್ಕೆ ಶೃಂಗವನ್ನು ಹೊಂದಿರುವ ಸಹಾಯಕ ರೇಖಾಚಿತ್ರವನ್ನು ರಚಿಸಿ ಮತ್ತು ಪ್ರತಿ ಜೋಡಿ ಟಿ-ವಿರುದ್ಧ ಅಂಚುಗಳಿಗೆ ಒಂದು ಅಂಚನ್ನು ರಚಿಸಿ, ಮತ್ತು ಈ ಸಹಾಯಕ ರೇಖಾಚಿತ್ರವು ಉಭಯಪಕ್ಷೀಯವಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ. ಈ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿಸುವುದು ಇನ್ಪುಟ್ ಗ್ರಾಫ್ನಲ್ಲಿನ ಎಲ್ಲಾ ಅಂಚಿನ ಜೋಡಿಗಳ ನಡುವಿನ ಸಂಬಂಧವನ್ನು ನಿರ್ಧರಿಸದೆ ಈ ವಿಧಾನವನ್ನು ನಿರ್ವಹಿಸಲು ಸಾಕಾಗುವ ಟಿ-ಅಲೈಕ್ ಮತ್ತು ಟಿ-ವಿರುದ್ಧ ಜೋಡಿಗಳ ಉಪವಿಭಾಗವನ್ನು ಕಂಡುಹಿಡಿಯುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಹೆಚ್ಚಿನ ಓದುವಿಕೆ ಟೋಪೋಲಾಜಿಕಲ್ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು