Halin graph
ರೇಖಾಚಿತ್ರ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಹ್ಯಾಲಿನ್ ರೇಖಾಚಿತ್ರವು ಒಂದು ರೀತಿಯ ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರವಾಗಿದ್ದು, ಇದನ್ನು ಮರದ ಎಲೆಗಳನ್ನು ಒಂದು ಚಕ್ರಕ್ಕೆ ಜೋಡಿಸುವ ಮೂಲಕ ನಿರ್ಮಿಸಲಾಗಿದೆ. ಮರವು ಕನಿಷ್ಠ ನಾಲ್ಕು ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರಬೇಕು, ಅವುಗಳಲ್ಲಿ ಯಾವುದೂ ನಿಖರವಾಗಿ ಎರಡು ನೆರೆಹೊರೆಗಳನ್ನು ಹೊಂದಿಲ್ಲ; ಅದನ್ನು ಸಮತಲದಲ್ಲಿ ಎಳೆಯಬೇಕು ಆದ್ದರಿಂದ ಅದರ ಯಾವುದೇ ಅಂಚುಗಳು ದಾಟುವುದಿಲ್ಲ (ಇದನ್ನು ಪ್ಲ್ಯಾನರ್ ಎಂಬೆಡಿಂಗ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ), ಮತ್ತು ಚಕ್ರವು ಎಲೆಗಳನ್ನು ಅವುಗಳ ಪ್ರದಕ್ಷಿಣಾಕಾರ ಕ್ರಮದಲ್ಲಿ ಈ ಎಂಬೆಡಿಂಗ್ನಲ್ಲಿ ಸಂಪರ್ಕಿಸುತ್ತದೆ. ಹೀಗಾಗಿ, ಚಕ್ರವು ಅದರೊಳಗಿನ ಮರದೊಂದಿಗೆ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ನ ಹೊರಗಿನ ಮುಖವನ್ನು ರೂಪಿಸುತ್ತದೆ. 1971ರಲ್ಲಿ ಅವುಗಳನ್ನು ಅಧ್ಯಯನ ಮಾಡಿದ ಜರ್ಮನ್ ಗಣಿತಶಾಸ್ತ್ರಜ್ಞ ರುಡಾಲ್ಫ್ ಹ್ಯಾಲಿನ್ ಅವರ ಹೆಸರನ್ನು ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳಿಗೆ ಇಡಲಾಗಿದೆ. ಕ್ಯೂಬಿಕ್ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳು-ಪ್ರತಿ ಶೃಂಗವು ನಿಖರವಾಗಿ ಮೂರು ಅಂಚುಗಳನ್ನು ಸ್ಪರ್ಶಿಸುವಂತಹವುಗಳನ್ನು ಕಿರ್ಕ್ಮನ್ ಈಗಾಗಲೇ ಒಂದು ಶತಮಾನದ ಹಿಂದೆ ಅಧ್ಯಯನ ಮಾಡಿದ್ದರು. ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳು ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ಗಳಾಗಿವೆ, ಅಂದರೆ ಪ್ರತಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ಅನ್ನು ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಹೆಡ್ರಾನ್ನ ಶೃಂಗಗಳು ಮತ್ತು ಅಂಚುಗಳನ್ನು ರೂಪಿಸಲು ಬಳಸಬಹುದು, ಮತ್ತು ಅವುಗಳಿಂದ ರೂಪುಗೊಂಡ ಪಾಲಿಹೆಡ್ರಾವನ್ನು ಛಾವಣಿಯಿಲ್ಲದ ಪಾಲಿಹೆಡ್ರಾ ಅಥವಾ ಗುಮ್ಮಟಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ತನ್ನ ಎಲ್ಲಾ ಶೃಂಗಗಳ ಮೂಲಕ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವನ್ನು ಹೊಂದಿದೆ, ಜೊತೆಗೆ ಗ್ರಾಫ್ನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯವರೆಗೆ ಬಹುತೇಕ ಎಲ್ಲಾ ಉದ್ದಗಳ ಚಕ್ರಗಳನ್ನು ಹೊಂದಿದೆ. ಹ್ಯಾಲಿನ್ ರೇಖಾಚಿತ್ರಗಳನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಗುರುತಿಸಬಹುದು. ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳು ಕಡಿಮೆ ತ್ರಿ ಅಗಲವನ್ನು ಹೊಂದಿರುವುದರಿಂದ, ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವಂತಹ ಇತರ ರೀತಿಯ ಸಮತಟ್ಟಾದ ಗ್ರಾಫ್ಗಳ ಮೇಲೆ ಕಠಿಣವಾಗಿರುವ ಅನೇಕ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಗಳನ್ನು ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ತ್ವರಿತವಾಗಿ ಪರಿಹರಿಸಬಹುದು. ಉದಾಹರಣೆಗಳು ನಕ್ಷತ್ರವು ನಿಖರವಾಗಿ ಒಂದು ಆಂತರಿಕ ಶೃಂಗವನ್ನು ಹೊಂದಿರುವ ಮರವಾಗಿದೆ. ಒಂದು ನಕ್ಷತ್ರಕ್ಕೆ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ರಚನೆಯನ್ನು ಅನ್ವಯಿಸುವುದರಿಂದ ಚಕ್ರದ ಗ್ರಾಫ್ ಅನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ, ಇದು ಪಿರಮಿಡ್ನ (ಅಂಚುಗಳ) ಗ್ರಾಫ್ ಆಗಿದೆ. ತ್ರಿಕೋನ ಪ್ರಿಸ್ಮ್ನ ರೇಖಾಚಿತ್ರವು ಸಹ ಹ್ಯಾಲಿನ್ ರೇಖಾಚಿತ್ರವಾಗಿದೆಃ ಇದನ್ನು ಎಳೆಯಬಹುದು, ಆದ್ದರಿಂದ ಅದರ ಆಯತಾಕಾರದ ಮುಖಗಳಲ್ಲಿ ಒಂದು ಬಾಹ್ಯ ಚಕ್ರವಾಗಿದೆ, ಮತ್ತು ಉಳಿದ ಅಂಚುಗಳು ನಾಲ್ಕು ಎಲೆಗಳು, ಎರಡು ಆಂತರಿಕ ಶೃಂಗಗಳು ಮತ್ತು ಐದು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಮರವನ್ನು ರೂಪಿಸುತ್ತವೆ. ಯಾವುದೇ ಕ್ಷುಲ್ಲಕವಲ್ಲದ ಗ್ರಾಫ್ ಆಟೋಮಾರ್ಫಿಸಮ್ಗಳಿಲ್ಲದ ಐದು ಚಿಕ್ಕ ಘನ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಒಂದಾದ ಫ್ರುಕ್ಟ್ ಗ್ರಾಫ್ ಸಹ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ಆಗಿದೆ. ಗುಣಲಕ್ಷಣಗಳು ಪ್ರತಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ 3-ಸಂಪರ್ಕಿತವಾಗಿದೆ, ಅಂದರೆ ಅದರಿಂದ ಎರಡು ಶೃಂಗಗಳನ್ನು ಅಳಿಸಲು ಮತ್ತು ಉಳಿದ ಶೃಂಗಗಳನ್ನು ಸಂಪರ್ಕ ಕಡಿತಗೊಳಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ. ಇದು ಎಡ್ಜ್-ಮಿನಿಮಲ್ 3-ಸಂಪರ್ಕಿತವಾಗಿದೆ, ಅಂದರೆ ಅದರ ಯಾವುದೇ ಒಂದು ಅಂಚನ್ನು ತೆಗೆದುಹಾಕಿದರೆ, ಉಳಿದ ಗ್ರಾಫ್ ಇನ್ನು ಮುಂದೆ 3-ಸಂಪರ್ಕಿತವಾಗಿರುವುದಿಲ್ಲ. ಸ್ಟೈನಿಟ್ಜ್ನ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, 3-ಸಂಪರ್ಕಿತ ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರವಾಗಿ, ಇದನ್ನು ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಹೆಡ್ರಾನ್ನ ಶೃಂಗಗಳು ಮತ್ತು ಅಂಚುಗಳ ಗುಂಪಾಗಿ ಪ್ರತಿನಿಧಿಸಬಹುದು; ಅಂದರೆ, ಇದು ಪಾಲಿಹೆಡ್ರಲ್ ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ಗ್ರಾಫ್ ಅನ್ನು ಅರಿತುಕೊಳ್ಳುವ ಪಾಲಿಹೆಡ್ರನ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಬಹುದು, ಇದರಿಂದಾಗಿ ಎಲ್ಲಾ ಮರದ ಎಲೆಗಳನ್ನು ಹೊಂದಿರುವ ಮುಖವು ಸಮತಲವಾಗಿರುತ್ತದೆ ಮತ್ತು ಇತರ ಎಲ್ಲಾ ಮುಖಗಳು ಅದರ ಮೇಲೆ ಸಮಾನ ಇಳಿಜಾರುಗಳೊಂದಿಗೆ ಇರುತ್ತವೆ. ಪ್ರತಿ ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ನಂತೆಯೇ, ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳು ಅದರ ಯಾವ ಮುಖವು ಹೊರಗಿನ ಮುಖವಾಗಿರಬೇಕು ಎಂಬುದರ ಆಯ್ಕೆಯವರೆಗೆ ವಿಶಿಷ್ಟವಾದ ಸಮತಟ್ಟಾದ ಎಂಬೆಡಿಂಗ್ ಅನ್ನು ಹೊಂದಿವೆ. ಪ್ರತಿ ಹ್ಯಾಲಿನ್ ರೇಖಾಚಿತ್ರವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ರೇಖಾಚಿತ್ರವಾಗಿದೆ ಮತ್ತು ರೇಖಾಚಿತ್ರದ ಪ್ರತಿ ತುದಿಯು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರಕ್ಕೆ ಸೇರಿದೆ. ಇದಲ್ಲದೆ, ಯಾವುದೇ ಶೃಂಗವನ್ನು ಅಳಿಸಿದ ನಂತರ ಯಾವುದೇ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿ ಉಳಿಯುತ್ತದೆ. ಡಿಗ್ರಿ 2 ರ ಶೃಂಗಗಳಿಲ್ಲದ ಪ್ರತಿಯೊಂದು ಮರವು ಒಂದೇ ಮೂಲವನ್ನು ಹಂಚಿಕೊಳ್ಳುವ ಎರಡು ಎಲೆಗಳನ್ನು ಹೊಂದಿರುವುದರಿಂದ, ಪ್ರತಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ತ್ರಿಕೋನವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಹ್ಯಾಲಿನ್ ರೇಖಾಚಿತ್ರವು ತ್ರಿಕೋನ-ಮುಕ್ತ ರೇಖಾಚಿತ್ರವಾಗಲಿ ಅಥವಾ ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರವಾಗಲಿ ಇರಲು ಸಾಧ್ಯವಿಲ್ಲ. ಹೆಚ್ಚು ಬಲವಾಗಿ, ಪ್ರತಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ಬಹುತೇಕ ಪ್ಯಾನ್ಸೈಕ್ಲಿಕ್ ಆಗಿದೆ, ಅಂದರೆ ಇದು ಒಂದೇ ಸಮ ಉದ್ದದ ಸಂಭವನೀಯ ಹೊರತುಪಡಿಸಿ 3 ರಿಂದ n ವರೆಗಿನ ಎಲ್ಲಾ ಉದ್ದಗಳ ಚಕ್ರಗಳನ್ನು ಹೊಂದಿದೆ. ಇದಲ್ಲದೆ, ಒಂದು ತುದಿಯನ್ನು ಸಂಕುಚಿತಗೊಳಿಸಿದರೆ ಯಾವುದೇ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ಬಹುತೇಕ ಪ್ಯಾನ್ಸೈಕ್ಲಿಕ್ ಆಗಿ ಉಳಿಯುತ್ತದೆ ಮತ್ತು ಡಿಗ್ರಿ ಮೂರು ಆಂತರಿಕ ಶೃಂಗಗಳಿಲ್ಲದ ಪ್ರತಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ಪ್ಯಾನ್ಸೈಕ್ಲಿಕ್ ಆಗಿರುತ್ತದೆ. ಗರಿಷ್ಠ ಡಿಗ್ರಿ ನಾಲ್ಕಕ್ಕಿಂತ ಹೆಚ್ಚಿರುವ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ನ ಇನ್ಸಿಡೆನ್ಸ್ ಕ್ರೊಮ್ಯಾಟಿಕ್ ಸಂಖ್ಯೆ. ಇದು ಎಲ್ಲಾ ಜೋಡಿಗಳಿಗೆ (ವಿ, ಇ) ಬಣ್ಣ ನೀಡಲು ಅಗತ್ಯವಿರುವ ಬಣ್ಣಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ, ಅಲ್ಲಿ ವಿ ಗ್ರಾಫ್ನ ಶೃಂಗವಾಗಿದೆ, ಮತ್ತು ಇ ಬಣ್ಣದಲ್ಲಿ ಕೆಲವು ನಿರ್ಬಂಧಗಳನ್ನು ಅನುಸರಿಸಿ, ವಿ ಗೆ ಅಂಚಿನ ಘಟನೆಯಾಗಿದೆ. ಶೃಂಗವನ್ನು ಹಂಚಿಕೊಳ್ಳುವ ಅಥವಾ ಅಂಚನ್ನು ಹಂಚಿಕೊಳ್ಳುವ ಜೋಡಿಗಳು ಒಂದೇ ಬಣ್ಣವನ್ನು ಹೊಂದಲು ಅನುಮತಿಸಲಾಗುವುದಿಲ್ಲ. ಇದಲ್ಲದೆ, ಒಂದು ಜೋಡಿ (ವಿ, ಇ) ಇ ನ ಇತರ ಅಂತಿಮ ಬಿಂದುವನ್ನು ಬಳಸುವ ಮತ್ತೊಂದು ಜೋಡಿಯ ಅದೇ ಬಣ್ಣವನ್ನು ಹೊಂದಿರಬಾರದು. ಅಥವಾ ಹೊಂದಿರುವ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳಿಗೆ, ಇನ್ಸಿಡೆನ್ಸ್ ಕ್ರೊಮ್ಯಾಟಿಕ್ ಸಂಖ್ಯೆಯು ಅನುಕ್ರಮವಾಗಿ ಅಥವಾ ದೊಡ್ಡದಾಗಿರಬಹುದು. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ರೇಖಾಚಿತ್ರದ ಪ್ಲ್ಯಾನರ್ ಎಂಬೆಡಿಂಗ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮೂಲಕ (ಒಂದು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ), ಮತ್ತು ನಂತರ ಕನಿಷ್ಠ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಮುಖವಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುವ ಮೂಲಕ, ನೀಡಲಾದ-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ಆಗಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸಲು ಸಾಧ್ಯವಿದೆ. ಹಾಗಿದ್ದಲ್ಲಿ, ಅಂತಹ ನಾಲ್ಕು ಮುಖಗಳು ಇರಬಹುದು, ಮತ್ತು ಅವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದಕ್ಕೂ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಶೀಲಿಸಲು ಸಾಧ್ಯವಿದೆ, ಉಳಿದ ಗ್ರಾಫ್ ಈ ಮುಖದ ಶೃಂಗಗಳನ್ನು ಅದರ ಎಲೆಗಳಾಗಿ ಹೊಂದಿರುವ ಮರವನ್ನು ರೂಪಿಸುತ್ತದೆಯೇ ಎಂದು. ಮತ್ತೊಂದೆಡೆ, ಅಂತಹ ಯಾವುದೇ ಮುಖ ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲದಿದ್ದರೆ, ಗ್ರಾಫ್ ಹ್ಯಾಲಿನಲ್ಲ. ಪರ್ಯಾಯವಾಗಿ, ಶೃಂಗಗಳು ಮತ್ತು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ ಸಮತಟ್ಟಾಗಿದ್ದರೆ, 3-ಸಂಪರ್ಕಿತವಾಗಿದ್ದರೆ ಮತ್ತು ಅದರ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯು ಗ್ರಾಫ್ನ ಸರ್ಕ್ಯೂಟ್ ಶ್ರೇಣಿಗೆ ಸಮನಾಗಿದ್ದರೆ ಮಾತ್ರ ಹ್ಯಾಲಿನ್ ಆಗಿರುತ್ತದೆ, ಇವೆಲ್ಲವನ್ನೂ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಶೀಲಿಸಬಹುದು. ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳನ್ನು ಗುರುತಿಸುವ ಇತರ ವಿಧಾನಗಳಲ್ಲಿ ಕೊರ್ಸೆಲ್ಲೆಯ ಪ್ರಮೇಯದ ಅನ್ವಯ ಅಥವಾ ಗ್ರಾಫ್ ಮರುಬರಹವನ್ನು ಆಧರಿಸಿದ ವಿಧಾನವು ಸೇರಿವೆ, ಇವುಗಳಲ್ಲಿ ಯಾವುದೂ ಗ್ರಾಫ್ನ ಪ್ಲ್ಯಾನರ್ ಎಂಬೆಡಿಂಗ್ ಅನ್ನು ತಿಳಿದುಕೊಳ್ಳುವುದರ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿಲ್ಲ. ಪ್ರತಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ ಮೂರು ಅಗಲ = 3 ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಅನಿಯಂತ್ರಿತ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಿಗೆ ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿರುವ ಅನೇಕ ಗ್ರಾಫ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳು, ಉದಾಹರಣೆಗೆ ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಸೆಟ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು, ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅಥವಾ ಕೊರ್ಸೆಲ್ಲೆ ಪ್ರಮೇಯವನ್ನು ಬಳಸಿಕೊಂಡು ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಅಥವಾ ಕೆಲವು ಸಂದರ್ಭಗಳಲ್ಲಿ (ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರಗಳ ನಿರ್ಮಾಣದಂತಹ) ನೇರ ಕ್ರಮಾವಳಿಗಳಿಂದ ಪರಿಹರಿಸಬಹುದು. ಆದಾಗ್ಯೂ, ಕೊಟ್ಟಿರುವ ಗ್ರಾಫ್ನ ಎಲ್ಲಾ ಶೃಂಗಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಹ್ಯಾಲಿನ್ ಸಬ್ಗ್ರಾಫ್ ಇದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸಲು ಅಥವಾ ಕೊಟ್ಟಿರುವ ಗ್ರಾಫ್ ದೊಡ್ಡ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ನ ಸಬ್ಗ್ರಾಫ್ ಆಗಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸಲು, ಕೊಟ್ಟಿರುವ ಗ್ರಾಫ್ನ ಅತಿದೊಡ್ಡ ಹ್ಯಾಲಿನ್ ಸಬ್ಗ್ರಾಫ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿದೆ. 1971ರಲ್ಲಿ, ಹ್ಯಾಲಿನ್ ಕನಿಷ್ಠ 3-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ಗಳ ವರ್ಗವಾಗಿ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳನ್ನು ಪರಿಚಯಿಸಿದರುಃ ಗ್ರಾಫ್ನಲ್ಲಿನ ಪ್ರತಿ ಅಂಚಿಗೆ, ಆ ಅಂಚನ್ನು ತೆಗೆದುಹಾಕುವುದರಿಂದ ಗ್ರಾಫ್ನ ಸಂಪರ್ಕವನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ಅನಿಯಂತ್ರಿತ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಿಗೆ ಗಣನೆಗೆ ಅಸಾಧ್ಯವಾದ ಅನೇಕ ಅಲ್ಗಾರಿದಮಿಕ್ ಸಮಸ್ಯೆಗಳನ್ನು ಅವುಗಳ ಮೇಲೆ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರಿಹರಿಸಬಹುದು ಎಂಬ ಆವಿಷ್ಕಾರದೊಂದಿಗೆ ಈ ಗ್ರಾಫ್ಗಳು ಮಹತ್ವವನ್ನು ಗಳಿಸಿದವು. ಈ ಸತ್ಯವನ್ನು ನಂತರ ಅವುಗಳ ಕಡಿಮೆ ತ್ರಿ-ಅಗಲ ಮತ್ತು ಕಡಿಮೆ ತ್ರಿ-ಅಗಲದ ಯಾವುದೇ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಈ ಸಮಸ್ಯೆಗಳಿಗೆ ಪರಿಣಾಮಕಾರಿ ಪರಿಹಾರಗಳನ್ನು ಒದಗಿಸುವ ಕೊರ್ಸೆಲ್ನ ಪ್ರಮೇಯದಂತಹ ಕ್ರಮಾವಳಿಗಳ ಮೆಟಾ-ಪ್ರಮೇಯಗಳ ಪರಿಣಾಮವೆಂದು ವಿವರಿಸಲಾಯಿತು. ಈ ಗ್ರಾಫ್ಗಳ ಮೇಲೆ ಹ್ಯಾಲಿನ್ ಕೆಲಸ ಮಾಡುವ ಮೊದಲು, ಕ್ಯೂಬಿಕ್ (ಅಥವಾ 3-ನಿಯಮಿತ) ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ಗ್ರಾಫ್ ಎಣಿಕೆ ಸಮಸ್ಯೆಗಳನ್ನು 1856ರಲ್ಲಿ ಥಾಮಸ್ ಕಿರ್ಕ್ಮನ್ ಮತ್ತು 1965ರಲ್ಲಿ ಹ್ಯಾನ್ಸ್ ರಾಡೆಮಾಚೆರ್ ಅಧ್ಯಯನ ಮಾಡಿದರು. ರಾಡೆಮಾಚೆರ್ ಈ ಗ್ರಾಫ್ಗಳನ್ನು ಪಾಲಿಹೆಡ್ರಾ ಆಧಾರಿತ ಎಂದು ಕರೆಯುತ್ತಾರೆ. ಅವರು ಅವುಗಳನ್ನು ಒಂದು ಮುಖವು ಬದಿಗಳನ್ನು ಹೊಂದಿರುವ ಮುಖಗಳನ್ನು ಹೊಂದಿರುವ ಘನ ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ಗಳು ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತಾರೆ. ಈ ವ್ಯಾಖ್ಯಾನಕ್ಕೆ ಸರಿಹೊಂದುವ ಗ್ರಾಫ್ಗಳು ನಿಖರವಾಗಿ ಕ್ಯೂಬಿಕ್ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳಾಗಿವೆ. ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳು ಮತ್ತು 4-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು ಎರಡೂ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ ಎಂಬ ಅಂಶದಿಂದ ಸ್ಫೂರ್ತಿ ಪಡೆದಿವೆ, ಪ್ರತಿ 4-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ ವಿಸ್ತರಿತ ಹ್ಯಾಲಿನ್ ಉಪಗ್ರಾಫ್ ಅನ್ನು ಹೊಂದಿದೆ ಎಂದು ಊಹಿಸಲಾಗಿದೆ; ಇಲ್ಲಿ "ಸ್ಪ್ಯಾನಿಂಗ್" ಎಂದರೆ ಉಪಗ್ರಾಫ್ ದೊಡ್ಡ ಗ್ರಾಫ್ನ ಎಲ್ಲಾ ಶೃಂಗಗಳನ್ನು ಒಳಗೊಂಡಿದೆ ಎಂದರ್ಥ. ಲೊವಾಸ್ಜ್-ಪ್ಲಮ್ಮರ್ ಊಹೆಯು 2015 ರವರೆಗೆ ತೆರೆದಿತ್ತು, ಅನಂತವಾದ ಅನೇಕ ಪ್ರತಿರೂಪಗಳ ನಿರ್ಮಾಣವನ್ನು ಪ್ರಕಟಿಸಲಾಯಿತು. ಹ್ಯಾಲಿನ್ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಕೆಲವೊಮ್ಮೆ ಸ್ಕರ್ಟ್ ಮರಗಳು ಅಥವಾ ಛಾವಣಿಯಿಲ್ಲದ ಪಾಲಿಹೆಡ್ರಾ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಈ ಹೆಸರುಗಳು ಅಸ್ಪಷ್ಟವಾಗಿವೆ. ಕೆಲವು ಲೇಖಕರು ಮರಗಳ ಎಲೆಗಳನ್ನು ಒಂದು ಚಕ್ರಕ್ಕೆ ಜೋಡಿಸುವ ಮೂಲಕ ರೂಪುಗೊಂಡ ಸಮತಟ್ಟಾದ ನಕ್ಷೆಗಳನ್ನು ಉಲ್ಲೇಖಿಸಲು "ಸ್ಕರ್ಟ್ಡ್ ಟ್ರೀಸ್" ಎಂಬ ಹೆಸರನ್ನು ಬಳಸುತ್ತಾರೆ, ಆದರೆ ಮರದ ಆಂತರಿಕ ಶೃಂಗಗಳು ಮೂರು ಅಥವಾ ಅದಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಡಿಗ್ರಿಗಳನ್ನು ಹೊಂದಿರಬೇಕಾಗಿಲ್ಲ. ಮತ್ತು "ಬೇಸ್ಡ್ ಪಾಲಿಹೆಡ್ರ" ನಂತೆ, "ರೂಫ್ ಲೆಸ್ ಪಾಲಿಹೆಡ್ರ" ಎಂಬ ಹೆಸರು ಕ್ಯೂಬಿಕ್ ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳನ್ನು ಸಹ ಉಲ್ಲೇಖಿಸಬಹುದು. ಹ್ಯಾಲಿನ್ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಹೊಂದಿರುವ ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಹೆಡ್ರಾವನ್ನು ಗುಮ್ಮಟಗಳು ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳು, ಗ್ರಾಫ್ ವರ್ಗ ಸೇರ್ಪಡೆಗಳ ಮಾಹಿತಿ ವ್ಯವಸ್ಥೆ. ಗ್ರಾಫ್ ಕುಟುಂಬಗಳು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು