Twin-width
ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ನ ಅವಳಿ-ಅಗಲವು ಗ್ರಾಫ್ಗೆ ಸಂಬಂಧಿಸಿದ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಯಾಗಿದ್ದು, ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳ ನಿಯತಾಂಕ ಸಂಕೀರ್ಣತೆಯನ್ನು ಅಧ್ಯಯನ ಮಾಡಲು ಬಳಸಲಾಗುತ್ತದೆ. ಅಂತರ್ಬೋಧೆಯಿಂದ, ಇದು ರೇಖಾಚಿತ್ರವು ರೇಖಾಚಿತ್ರಕ್ಕೆ ಎಷ್ಟು ಹೋಲುತ್ತದೆ ಎಂಬುದನ್ನು ಅಳೆಯುತ್ತದೆ, ಇದು ಒಂದೇ ನೆರೆಯವರನ್ನು ಹೊಂದಿರುವ ಅವಳಿ, ಶೃಂಗಗಳನ್ನು ಪದೇ ಪದೇ ಒಗ್ಗೂಡಿಸುವ ಮೂಲಕ ಒಂದೇ ಶೃಂಗಕ್ಕೆ ಇಳಿಸಬಹುದಾದ ರೇಖಾಚಿತ್ರದ ಒಂದು ವಿಧವಾಗಿದೆ. ಅವಳಿ-ಅಗಲವನ್ನು ಪುನರಾವರ್ತಿತ ವಿಲೀನಗಳ ಅನುಕ್ರಮದಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ, ಅಲ್ಲಿ ಶೃಂಗಗಳು ಅವಳಿಗಳಾಗಿರಬೇಕಾಗಿಲ್ಲ, ಆದರೆ ನೆರೆಹೊರೆಯವರ ಸುಮಾರು ಸಮಾನ ಗುಂಪುಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ. ವ್ಯಾಖ್ಯಾನ ಅವಳಿ-ಅಗಲವನ್ನು ಸೀಮಿತ ಸರಳ ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ಗಳಿಗೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಇವುಗಳು ಸೀಮಿತವಾದ ಶೃಂಗಗಳ ಗುಂಪನ್ನು ಮತ್ತು ಕ್ರಮಬದ್ಧವಲ್ಲದ ಜೋಡಿ ಶೃಂಗಗಳ ಅಂಚುಗಳ ಗುಂಪನ್ನು ಹೊಂದಿವೆ. ಯಾವುದೇ ಶೃಂಗದ ತೆರೆದ ನೆರೆಹೊರೆಯು ಗ್ರಾಫ್ನ ಅಂಚುಗಳಲ್ಲಿ ಜೋಡಿಯಾಗಿರುವ ಇತರ ಶೃಂಗಗಳ ಗುಂಪಾಗಿದೆ; ಮುಕ್ತ ನೆರೆಹೊರೆಯಿಂದ ಮುಚ್ಚಿದ ನೆರೆಹೊರೆಯು ಶೃಂಗವನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ರೂಪುಗೊಳ್ಳುತ್ತದೆ. ಎರಡು ಶೃಂಗಗಳು ಒಂದೇ ಮುಚ್ಚಿದ ನೆರೆಹೊರೆಯನ್ನು ಹೊಂದಿರುವಾಗ ನಿಜವಾದ ಅವಳಿಗಳು, ಮತ್ತು ಒಂದೇ ತೆರೆದ ನೆರೆಹೊರೆಯನ್ನು ಹೊಂದಿರುವಾಗ ಸುಳ್ಳು ಅವಳಿಗಳು; ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ನಿಜವಾದ ಅವಳಿಗಳು ಮತ್ತು ಸುಳ್ಳು ಅವಳಿಗಳನ್ನು ಅರ್ಹತೆಯಿಲ್ಲದೆ ಅವಳಿಗಳು ಎಂದು ಕರೆಯಬಹುದು. ಆಲೇಖನಗಳು ಅನೇಕ ಸಮಾನ ವ್ಯಾಖ್ಯಾನಗಳನ್ನು ಹೊಂದಿವೆ, ಆದರೆ ಅವುಗಳಲ್ಲಿ ಒಂದು, ಯಾವುದೇ ಎರಡು ಅವಳಿ ಶೃಂಗಗಳನ್ನು ಪದೇ ಪದೇ ಕಂಡುಹಿಡಿಯುವ ಮತ್ತು ಅವುಗಳನ್ನು ಒಂದೇ ಶೃಂಗದಲ್ಲಿ ವಿಲೀನಗೊಳಿಸುವ ಪ್ರಕ್ರಿಯೆಯ ಮೂಲಕ ಒಂದೇ ಶೃಂಗಕ್ಕೆ ಇಳಿಸಬಹುದಾದ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ. ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಯಾವ ಅವಳಿಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಬೇಕೆಂದು ಆಯ್ಕೆ ಮಾಡಿದರೂ, ಈ ಕಡಿತ ಪ್ರಕ್ರಿಯೆಯು ಯಾವಾಗಲೂ ಯಶಸ್ವಿಯಾಗುತ್ತದೆ. ಗ್ರಾಫ್ನಲ್ಲದ ಗ್ರಾಫ್ಗಾಗಿ, ಅದು ಯಾವಾಗಲೂ ಅವಳಿಗಳಿಲ್ಲದ ಎರಡಕ್ಕಿಂತ ಹೆಚ್ಚು ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಉಪಗ್ರಾಫ್ನಲ್ಲಿ ಸಿಲುಕಿಕೊಳ್ಳುತ್ತದೆ. ಅವಳಿ-ಅಗಲದ ವ್ಯಾಖ್ಯಾನವು ಈ ಕಡಿತ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಅನುಕರಿಸುತ್ತದೆ. ಸಂಕೋಚನದ ಅನುಕ್ರಮವು, ಈ ಸಂದರ್ಭದಲ್ಲಿ, ನೀಡಲಾದ ರೇಖಾಚಿತ್ರದಿಂದ ಪ್ರಾರಂಭವಾಗುವ ಹಂತಗಳ ಅನುಕ್ರಮವಾಗಿದೆ, ಇದರಲ್ಲಿ ಪ್ರತಿ ಹಂತವು ಒಂದು ಜೋಡಿ ಶೃಂಗಗಳನ್ನು ಒಂದೇ ಶೃಂಗದಿಂದ ಬದಲಾಯಿಸುತ್ತದೆ. ಇದು ಕೆಂಪು ಮತ್ತು ಕಪ್ಪು ಬಣ್ಣದ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ರೇಖಾಚಿತ್ರಗಳ ಸರಣಿಯನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ; ಕೊಟ್ಟಿರುವ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಕಪ್ಪು ಎಂದು ಭಾವಿಸಲಾಗಿದೆ. ಎರಡು ಶೃಂಗಗಳನ್ನು ಒಂದೇ ಶೃಂಗದಿಂದ ಬದಲಾಯಿಸಿದಾಗ, ಹೊಸ ಶೃಂಗದ ನೆರೆಹೊರೆಯು ಬದಲಾದ ಶೃಂಗಗಳ ನೆರೆಹೊರೆಯ ಒಕ್ಕೂಟವಾಗಿದೆ. ಈ ಹೊಸ ನೆರೆಹೊರೆಯಲ್ಲಿ, ಎರಡೂ ಶೃಂಗಗಳ ನೆರೆಹೊರೆಯಲ್ಲಿ ಕಪ್ಪು ಅಂಚುಗಳಿಂದ ಬರುವ ಅಂಚು ಕಪ್ಪು ಬಣ್ಣದಲ್ಲಿ ಉಳಿಯುತ್ತದೆ; ಎಲ್ಲಾ ಇತರ ಅಂಚುಗಳು ಕೆಂಪು ಬಣ್ಣದಲ್ಲಿರುತ್ತವೆ. ಅನುಕ್ರಮದ ಉದ್ದಕ್ಕೂ, ಪ್ರತಿಯೊಂದು ಶೃಂಗವು ಹೆಚ್ಚಿನ ಕೆಂಪು ಅಂಚುಗಳನ್ನು ಮುಟ್ಟಿದರೆ ಸಂಕೋಚನದ ಅನುಕ್ರಮವನ್ನು-ಅನುಕ್ರಮ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ರೇಖಾಚಿತ್ರದ ಅವಳಿ-ಅಗಲವು ಅದು-ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿರುವ ಅತ್ಯಂತ ಚಿಕ್ಕ ಮೌಲ್ಯವಾಗಿದೆ. ದಟ್ಟವಾದ ರೇಖಾಚಿತ್ರವು ಇನ್ನೂ ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿರಬಹುದು; ಉದಾಹರಣೆಗೆ, ರೇಖಾಚಿತ್ರಗಳು ಎಲ್ಲಾ ಸಂಪೂರ್ಣ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತವೆ. ಅವಳಿ-ಅಗಲದ, ವಿರಳವಾದ ಅವಳಿ-ಅಗಲದ ವ್ಯತ್ಯಾಸವು, ಪ್ರತ್ಯೇಕ ಗ್ರಾಫ್ಗಳ ಬದಲಿಗೆ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳಿಗೆ ಅನ್ವಯಿಸುತ್ತದೆ. ಇಂಡ್ಯೂಸ್ಡ್ ಸಬ್ಗ್ರಾಫ್ಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ ಮುಚ್ಚಲ್ಪಟ್ಟಿರುವ ಮತ್ತು ಅವಳಿ-ಅಗಲವನ್ನು ಸುತ್ತುವರೆದಿರುವ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಕ್ಕೆ, ಈ ಕೆಳಗಿನ ಗುಣಲಕ್ಷಣಗಳು ಸಮಾನವಾಗಿವೆಃ ಕುಟುಂಬದಲ್ಲಿನ ಗ್ರಾಫ್ಗಳು ವಿರಳವಾಗಿರುತ್ತವೆ, ಅಂದರೆ ಅವು ತಮ್ಮ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯ ರೇಖೀಯ ಕಾರ್ಯದಿಂದ ಸುತ್ತುವರಿದ ಹಲವಾರು ಅಂಚುಗಳನ್ನು ಹೊಂದಿವೆ. ಈ ಕುಟುಂಬವು ಎಲ್ಲಾ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಒಳಗೊಂಡಿಲ್ಲ. ಕೊಟ್ಟಿರುವ ಕುಟುಂಬದಲ್ಲಿ ಗ್ರಾಫ್ಗಳ ಎಲ್ಲಾ ಉಪಗ್ರಾಫ್ಗಳ ಕುಟುಂಬವು ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿದೆ. ಕುಟುಂಬವು ಸೀಮಿತ ವಿಸ್ತರಣೆಯನ್ನು ಹೊಂದಿದೆ, ಅಂದರೆ ಅದರ ಎಲ್ಲಾ ಆಳವಿಲ್ಲದ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರು ವಿರಳವಾಗಿರುತ್ತಾರೆ. ಅಂತಹ ಕುಟುಂಬವು ವಿರಳವಾದ ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ. ಅವಳಿ-ಅಗಲದ ಪರಿಕಲ್ಪನೆಯನ್ನು ಗ್ರಾಫ್ಗಳಿಂದ ವಿವಿಧ ಸಂಪೂರ್ಣವಾಗಿ ಕ್ರಮಬದ್ಧವಾದ ರಚನೆಗಳವರೆಗೆ ಸಾಮಾನ್ಯೀಕರಿಸಬಹುದು (ಅವುಗಳ ಶೃಂಗಗಳ ಮೇಲೆ ಒಟ್ಟು ಕ್ರಮವನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳನ್ನು ಒಳಗೊಂಡಂತೆ), ಮತ್ತು ಕ್ರಮಬದ್ಧವಲ್ಲದ ಗ್ರಾಫ್ಗಳಿಗಿಂತ ಕ್ರಮಬದ್ಧವಾದ ರಚನೆಗಳಿಗೆ ಅನೇಕ ರೀತಿಯಲ್ಲಿ ಸರಳವಾಗಿದೆ. ಗ್ರಾಫ್ ಅಗಲದ ಇತರ ಕಲ್ಪನೆಗಳಿಗೆ ಸಮಾನವಾದ ವ್ಯಾಖ್ಯಾನಗಳನ್ನು ರೂಪಿಸಲು ಸಾಧ್ಯವಿದೆ, ಸಂಕೋಚನ ಅನುಕ್ರಮಗಳನ್ನು ಬಳಸಿಕೊಂಡು ವಿಭಿನ್ನ ಅವಶ್ಯಕತೆಗಳೊಂದಿಗೆ ಸೀಮಿತ ಮಟ್ಟವನ್ನು ಹೊಂದಿರುವುದಕ್ಕಿಂತ. ಸುತ್ತುವರಿದ ಅವಳಿ-ಅಗಲದ ರೇಖಾಚಿತ್ರಗಳ ರೇಖಾಚಿತ್ರಗಳು ಅವಳಿ-ಅಗಲ ಶೂನ್ಯವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಕಾಗ್ಗಳ ಕಡಿತ ಪ್ರಕ್ರಿಯೆಯಲ್ಲಿ, ಯಾವುದೇ ಕೆಂಪು ಅಂಚುಗಳಿರುವುದಿಲ್ಲಃ ಎರಡು ಶೃಂಗಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಿದಾಗ, ಅವುಗಳ ನೆರೆಹೊರೆಗಳು ಸಮಾನವಾಗಿರುತ್ತವೆ, ಆದ್ದರಿಂದ ಎರಡು ನೆರೆಹೊರೆಗಳಲ್ಲಿ ಒಂದರಿಂದ ಮಾತ್ರ ಕೆಂಪು ಬಣ್ಣಕ್ಕೆ ಬರುವ ಯಾವುದೇ ಅಂಚುಗಳಿರುವುದಿಲ್ಲ. ಬೇರೆ ಯಾವುದೇ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, ಯಾವುದೇ ಸಂಕೋಚನದ ಅನುಕ್ರಮವು ಕೆಲವು ಕೆಂಪು ಅಂಚುಗಳನ್ನು ಉಂಟುಮಾಡುತ್ತದೆ ಮತ್ತು ಅವಳಿ-ಅಗಲವು ಶೂನ್ಯಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ಗರಿಷ್ಠ ಮೂರು ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಪಥದ ರೇಖಾಚಿತ್ರಗಳು ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ, ಆದರೆ ಪ್ರತಿ ದೊಡ್ಡ ಪಥದ ರೇಖಾಚಿತ್ರವು ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಪಥದ ಕೊನೆಯ ಎರಡು ಅಂಚುಗಳನ್ನು ಪದೇ ಪದೇ ವಿಲೀನಗೊಳಿಸುವ ಸಂಕೋಚನ ಅನುಕ್ರಮಕ್ಕೆ, ಏಕ ವಿಲೀನಗೊಂಡ ಶೃಂಗಕ್ಕೆ ಅಂಚಿನ ಘಟನೆಯು ಮಾತ್ರ ಕೆಂಪು ಬಣ್ಣದ್ದಾಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಇದು 1-ಅನುಕ್ರಮವಾಗಿದೆ. ಮರಗಳು ಗರಿಷ್ಠ ಎರಡು ಅಗಲವನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ಕೆಲವು ಮರಗಳಿಗೆ ಇದು ಬಿಗಿಯಾಗಿರುತ್ತದೆ. ಯಾವುದೇ ಮರಕ್ಕೆ 2-ಸಂಕೋಚನದ ಅನುಕ್ರಮವನ್ನು ಒಂದು ಮೂಲವನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ ಕಂಡುಹಿಡಿಯಬಹುದು, ಮತ್ತು ನಂತರ ಒಂದೇ ಮೂಲವನ್ನು ಹೊಂದಿರುವ ಎರಡು ಎಲೆಗಳನ್ನು ಪದೇ ಪದೇ ವಿಲೀನಗೊಳಿಸಬಹುದು ಅಥವಾ ಇದು ಸಾಧ್ಯವಾಗದಿದ್ದರೆ, ಆಳವಾದ ಎಲೆಯನ್ನು ಅದರ ಮೂಲದಲ್ಲಿ ವಿಲೀನಗೊಳಿಸಬಹುದು. ಕೇವಲ ಕೆಂಪು ಅಂಚುಗಳು ಎಲೆಗಳನ್ನು ಅವುಗಳ ಪೋಷಕರಿಗೆ ಸಂಪರ್ಕಿಸುತ್ತವೆ, ಮತ್ತು ಒಂದೇ ಮೂಲದಲ್ಲಿ ಎರಡು ಇದ್ದಾಗ ಅವುಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಬಹುದು, ಕೆಂಪು ಮಟ್ಟವನ್ನು ಗರಿಷ್ಠ ಎರಡರಷ್ಟು ಇಟ್ಟುಕೊಳ್ಳಬಹುದು. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಈ ಕೆಳಗಿನ ವರ್ಗಗಳ ಗ್ರಾಫ್ಗಳು ಅವಳಿ-ಅಗಲವನ್ನು ಸುತ್ತುವರೆದಿವೆ, ಮತ್ತು ಅವುಗಳಿಗೆ ಸೀಮಿತ ಅಗಲದ ಸಂಕೋಚನ ಅನುಕ್ರಮವನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಕಾಣಬಹುದುಃ ಸೀಮಿತವಾದ ಗುಂಪಿನ-ಅಗಲದ ಅಥವಾ ಸೀಮಿತ ಶ್ರೇಣಿಯ-ಅಗಲದ ಪ್ರತಿಯೊಂದು ಗ್ರಾಫ್ ಸಹ ಅವಳಿ-ಅಗಲವನ್ನು ಸುತ್ತುವರೆದಿದೆ. ಅವಳಿ-ಅಗಲವು ಗುಂಪು-ಅಗಲದಲ್ಲಿ ಗರಿಷ್ಠ ಘಾತೀಯವಾಗಿರುತ್ತದೆ ಮತ್ತು ಶ್ರೇಣಿ-ಅಗಲದಲ್ಲಿ ಗರಿಷ್ಠ ದ್ವಿಗುಣ ಘಾತೀಯವಾಗಿರುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಈ ಗ್ರಾಫ್ಗಳು, ದೂರ-ಆನುವಂಶಿಕ ಗ್ರಾಫ್ಗಳು, ಮಿತಿಯ ಮೌಲ್ಯಗಳಿಗೆ-ಲೀಫ್ ಪವರ್ಗಳು ಮತ್ತು ಮಿತಿಯ ಮೂರು ಅಗಲದ ಗ್ರಾಫ್ಗಳನ್ನು ಒಳಗೊಂಡಿವೆ. ಉದಾಸೀನತೆಯ ರೇಖಾಚಿತ್ರಗಳು (ಸಮಾನವಾಗಿ, ಏಕಾಂಕ ಮಧ್ಯಂತರ ರೇಖಾಚಿತ್ರಗಳು ಅಥವಾ ಸರಿಯಾದ ಮಧ್ಯಂತರ ರೇಖಾಚಿತ್ರಗಳು) ಗರಿಷ್ಠ ಎರಡರಷ್ಟು ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಸಮತಲದ ಪ್ರತಿಯೊಂದು ಬಿಂದುವನ್ನು ಆವರಿಸುವ ಯುನಿಟ್ ಡಿಸ್ಕ್ಗಳ ಸೆಟ್ಗಳಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಯುನಿಟ್ ಡಿಸ್ಕ್ ಗ್ರಾಫ್ಗಳು ಸೀಮಿತ ಸಂಖ್ಯೆಯ ಬಾರಿ ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿವೆ. ಹೆಚ್ಚಿನ ಆಯಾಮಗಳಲ್ಲಿರುವ ಯುನಿಟ್ ಬಾಲ್ ಗ್ರಾಫ್ಗಳಿಗೂ ಇದು ಅನ್ವಯಿಸುತ್ತದೆ. ನಿಷೇಧಿತ ಕ್ರಮಪಲ್ಲಟನೆಯ ಮಾದರಿಯೊಂದಿಗೆ ಕ್ರಮಪಲ್ಲಟನೆಗಳಿಂದ ಬರುವ ಕ್ರಮಪಲ್ಲಟನೆಯ ರೇಖಾಚಿತ್ರಗಳು ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿವೆ. ಇದು ನಿಷೇಧಿತ ಮಾದರಿಗಳೊಂದಿಗೆ ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಮೇಲೆ ಅಲ್ಗಾರಿದಮಿಕ್ ಸಮಸ್ಯೆಗಳಿಗೆ ಅವಳಿ-ಅಗಲವನ್ನು ಅನ್ವಯಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಗ್ರಾಫ್ಗಳ ಪ್ರತಿಯೊಂದು ಕುಟುಂಬವು ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿದೆ. ಉದಾಹರಣೆಗೆ, ವ್ಯಾಗ್ನರ್ ಅವರ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಿಗೆ ನಿಷೇಧಿತ ಮೈನರ್ಗಳು ಎರಡು ಗ್ರಾಫ್ಗಳಾಗಿವೆ ಮತ್ತು ಆದ್ದರಿಂದ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿವೆ. ಬೌಂಡೆಡ್ ಸ್ಟ್ಯಾಕ್ ಸಂಖ್ಯೆ ಅಥವಾ ಬೌಂಡೆಡ್ ಕ್ಯೂ ಸಂಖ್ಯೆಯ ಪ್ರತಿಯೊಂದು ಗ್ರಾಫ್ ಕೂಡ ಬೌಂಡೆಡ್ ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿದೆ. ಬೌಂಡೆಡ್ ಸ್ಟಾಕ್ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರದ ಬೌಂಡೆಡ್ ಸ್ಪಾರ್ಸ್ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳಿವೆ, ಆದರೆ ಕ್ಯೂ ಸಂಖ್ಯೆಗೆ ಅನುಗುಣವಾದ ಪ್ರಶ್ನೆಯು ತೆರೆದಿರುತ್ತದೆ. ಬೌಂಡೆಡ್ ಅವಳಿ-ಅಗಲದ ಯಾವುದೇ ಎರಡು ಗ್ರಾಫ್ಗಳ ಬಲವಾದ ಉತ್ಪನ್ನ, ಅವುಗಳಲ್ಲಿ ಒಂದು ಬೌಂಡೆಡ್ ಡಿಗ್ರಿಯನ್ನು ಹೊಂದಿದೆ, ಮತ್ತೆ ಬೌಂಡೆಡ್ ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿದೆ. - ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಂತಹ ಬಲವಾದ ಪಥಗಳ ಉತ್ಪನ್ನಗಳಾಗಿ ಮತ್ತು ಸೀಮಿತ-ತ್ರಿ-ಅಗಲದ ಗ್ರಾಫ್ಗಳಾಗಿ ವಿಭಜನೆಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳ ವರ್ಗಗಳ ಸೀಮಿತ ಅವಳಿ-ಅಗಲವನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಇದನ್ನು ಬಳಸಬಹುದು. ಗ್ರಾಫ್ಗಳ ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕ್ ಉತ್ಪನ್ನಕ್ಕೆ, ಅವಳಿ-ಅಗಲವು ನಿಖರವಾಗಿ ಎರಡು ಅಂಶಗಳ ಗ್ರಾಫ್ಗಳ ಗರಿಷ್ಠ ಅಗಲವಾಗಿದೆ. ಅವಳಿ-ಅಗಲವು ಹಲವಾರು ಇತರ ಪ್ರಮಾಣಿತ ಗ್ರಾಫ್ ಉತ್ಪನ್ನಗಳ ಅಡಿಯಲ್ಲಿ ಉತ್ತಮವಾಗಿ ವರ್ತಿಸುತ್ತದೆ, ಆದರೆ ಗ್ರಾಫ್ಗಳ ಮಾಡ್ಯುಲರ್ ಉತ್ಪನ್ನವಲ್ಲ. ಬಂಧಿಸಲಾದ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ಗಳ ಪ್ರತಿಯೊಂದು ಆನುವಂಶಿಕ ಕುಟುಂಬದಲ್ಲಿ, ಅದರ ಗ್ರಾಫ್ಗಳ ಶೃಂಗಗಳಿಗೆ ಒಟ್ಟು ಆದೇಶಗಳ ಕುಟುಂಬವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಿದೆ, ಇದರಿಂದಾಗಿ ಪ್ರೇರಿತ ಉಪಗ್ರಫ್ನಲ್ಲಿ ಆನುವಂಶಿಕ ಕ್ರಮವು ಕುಟುಂಬದಲ್ಲಿ ಒಂದು ಕ್ರಮವಾಗಿದೆ, ಮತ್ತು ಈ ಆದೇಶಗಳಿಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಕುಟುಂಬವು ಚಿಕ್ಕದಾಗಿದೆ. ಇದರರ್ಥ, ಶೃಂಗಗಳ ಮೇಲಿನ ಒಟ್ಟು ಕ್ರಮಕ್ಕೆ, ಆ ಕ್ರಮಕ್ಕೆ ಅನುಗುಣವಾದ ಕುಟುಂಬದಲ್ಲಿನ ಗ್ರಾಫ್ಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠವಾಗಿ ಘಾತೀಯವಾಗಿರುತ್ತದೆ. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಈ ಅರ್ಥದಲ್ಲಿ ಚಿಕ್ಕದಾದ ಕ್ರಮಬದ್ಧ ಗ್ರಾಫ್ಗಳ ಪ್ರತಿಯೊಂದು ಆನುವಂಶಿಕ ಕುಟುಂಬವು ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿದೆ. ಚಿಕ್ಕದಾದ ಲೇಬಲ್ ಮಾಡಲಾದ ಗ್ರಾಫ್ಗಳ ಪ್ರತಿಯೊಂದು ಆನುವಂಶಿಕ ಕುಟುಂಬವು, ಗ್ರಾಫ್ಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠವಾಗಿ ಏಕವಾದ ಘಾತೀಯ ಅಂಶದ ಸಮಯವಾಗಿದೆ ಎಂಬ ಅರ್ಥದಲ್ಲಿ, ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಮೂಲತಃ ಊಹಿಸಲಾಗಿತ್ತು. ಆದಾಗ್ಯೂ, ಈ ಊಹೆಯನ್ನು ಅನಂತ ಕೇಲೆ ಗ್ರಾಫ್ನ ಪ್ರೇರಿತ ಉಪಗ್ರಾಫ್ಗಳ ಕುಟುಂಬವನ್ನು ಬಳಸಿಕೊಂಡು ನಿರಾಕರಿಸಲಾಗಿದೆ, ಅದು ಲೇಬಲ್ ಮಾಡಲಾದ ಗ್ರಾಫ್ಗಳಂತೆ ಚಿಕ್ಕದಾಗಿದೆ ಆದರೆ ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿಲ್ಲ. ಈ ಕೆಳಗಿನ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳಲ್ಲಿ ಮಿತಿಯಿಲ್ಲದ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ಗಳಿವೆಃ ಸೀಮಿತ ಮಟ್ಟದ ಗ್ರಾಫ್ಗಳು. ಮಧ್ಯಂತರ ರೇಖಾಚಿತ್ರಗಳು. ಯುನಿಟ್ ಡಿಸ್ಕ್ ರೇಖಾಚಿತ್ರಗಳು. ಈ ಪ್ರತಿಯೊಂದು ಪ್ರಕರಣಗಳಲ್ಲಿ, ಫಲಿತಾಂಶವು ಎಣಿಕೆಯ ವಾದವನ್ನು ಅನುಸರಿಸುತ್ತದೆಃ ಬದ್ಧ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ಗಳಿಗಿಂತ ನಿರ್ದಿಷ್ಟ ಪ್ರಕಾರದ ಹೆಚ್ಚಿನ ಗ್ರಾಫ್ಗಳಿವೆ. ಗುಣಲಕ್ಷಣಗಳು ಒಂದು ರೇಖಾಚಿತ್ರವು ಅವಳಿ-ಅಗಲವನ್ನು ಸುತ್ತುವರೆದಿದ್ದರೆ, ಸಂಕೋಚನಗಳ ಬಹುಮುಖ ಮರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಿದೆ. ಇದು ಸಂಕೋಚನ ಅನುಕ್ರಮಗಳ ಒಂದು ದೊಡ್ಡ ಕುಟುಂಬವಾಗಿದ್ದು, ಕೆಲವು (ದೊಡ್ಡ) ಸೀಮಿತ ಅಗಲವನ್ನು ಹೊಂದಿದೆ, ಆದ್ದರಿಂದ ಪ್ರತಿ ಅನುಕ್ರಮದಲ್ಲಿ ಪ್ರತಿ ಹಂತದಲ್ಲೂ ರೇಖೀಯವಾಗಿ ಅನೇಕ ಜೋಡಿಸದ ಜೋಡಿ ಶೃಂಗಗಳಿವೆ, ಪ್ರತಿಯೊಂದನ್ನೂ ಅನುಕ್ರಮದಲ್ಲಿ ಮುಂದಿನ ಹಂತದಲ್ಲಿ ಸಂಕುಚಿತಗೊಳಿಸಬಹುದು. ಇದರಿಂದ ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ಶೃಂಗಗಳ ಗುಂಪಿನ ಮೇಲೆ ಸುತ್ತುವರಿದ ಅವಳಿ-ಅಗಲದ ರೇಖಾಚಿತ್ರಗಳ ಸಂಖ್ಯೆಯು ಕೇವಲ ಏಕವಾದ ಘಾತೀಯ ಅಂಶಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದೆ, ಸುತ್ತುವರಿದ ಅವಳಿ-ಅಗಲದ ರೇಖಾಚಿತ್ರಗಳು ಪ್ರತಿ ಶೃಂಗಕ್ಕೆ ಬಿಟ್ಗಳ ಲಾಗರಿಥಮಿಕ್ ಸಂಖ್ಯೆಯನ್ನು ಮಾತ್ರ ಹೊಂದಿರುವ ಸಾಮೀಪ್ಯ ಲೇಬಲಿಂಗ್ ಯೋಜನೆಯನ್ನು ಹೊಂದಿವೆ ಮತ್ತು ಅವು ಬಹುಪದ ಗಾತ್ರದ ಸಾರ್ವತ್ರಿಕ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಹೊಂದಿವೆ, ಇದರಲ್ಲಿ ಸುತ್ತುವರಿದ ಅವಳಿ-ಅಗಲದ ಪ್ರತಿ-ಅಕ್ಷೀಯ ರೇಖಾಚಿತ್ರವನ್ನು ಪ್ರೇರಿತ ಉಪ-ರೇಖಾಚಿತ್ರವಾಗಿ ಕಾಣಬಹುದು. ಕ್ರಮಾವಳಿಗಳು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಅವಳಿ-ಅಗಲದ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಗರಿಷ್ಠ ಒಂದನ್ನು ಗುರುತಿಸಬಹುದು. ಆದಾಗ್ಯೂ, ನೀಡಲಾದ ರೇಖಾಚಿತ್ರವು ಗರಿಷ್ಠ ನಾಲ್ಕರಲ್ಲಿ ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸಲು NP-ಪೂರ್ಣವಾಗಿದೆ, ಮತ್ತು 5/4 ಕ್ಕಿಂತ ಉತ್ತಮವಾದ ಅಂದಾಜು ಅನುಪಾತದೊಂದಿಗೆ ಅವಳಿ-ಅಗಲವನ್ನು ಅಂದಾಜು ಮಾಡಲು NP-ಕಠಿಣವಾಗಿದೆ. ಘಾತೀಯ ಸಮಯದ ಊಹೆಯ ಅಡಿಯಲ್ಲಿ, ಅವಳಿ-ಅಗಲವನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳಲು-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಘಾತೀಯ ಸಮಯ ಬೇಕಾಗುತ್ತದೆ. ಪ್ರಾಯೋಗಿಕವಾಗಿ, ಎಸ್ಎಟಿ ಪರಿಹಾರಕಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಮಧ್ಯಮ ಗಾತ್ರದ ಗ್ರಾಫ್ಗಳ ಅವಳಿ-ಅಗಲವನ್ನು ಲೆಕ್ಕಹಾಕಲು ಸಾಧ್ಯವಿದೆ. ಸುತ್ತುವರಿದ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ಗಳ ತಿಳಿದಿರುವ ಹೆಚ್ಚಿನ ಕುಟುಂಬಗಳಿಗೆ, ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಸುತ್ತುವರಿದ ಅಗಲದ ಸಂಕೋಚನ ಅನುಕ್ರಮವನ್ನು ನಿರ್ಮಿಸಲು ಸಾಧ್ಯವಿದೆ. ಸಂಕೋಚನ ಅನುಕ್ರಮವನ್ನು ನೀಡಿದ ನಂತರ ಅಥವಾ ನಿರ್ಮಿಸಿದ ನಂತರ, ಅದನ್ನು ಬಳಸಿಕೊಂಡು ಅನೇಕ ವಿಭಿನ್ನ ಕ್ರಮಾವಳಿ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಬಹುದು, ಅನೇಕ ಸಂದರ್ಭಗಳಲ್ಲಿ ಅವಳಿ-ಅಗಲವನ್ನು ಹೊಂದಿರದ ಗ್ರಾಫ್ಗಳಿಗೆ ಸಾಧ್ಯವಾದಷ್ಟು ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿ. ಕೆಳಗೆ ವಿವರಿಸಿದಂತೆ, ಇವುಗಳು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಗಳಿಗೆ ನಿಖರವಾದ ನಿಯತಾಂಕ ಕ್ರಮಾವಳಿಗಳು ಮತ್ತು ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳನ್ನು ಒಳಗೊಂಡಿವೆ, ಜೊತೆಗೆ ಶಾಸ್ತ್ರೀಯ ಬಹುಪದ ಸಮಯ ಕ್ರಮಾವಳಿಗಳನ್ನು ಹೊಂದಿರುವ ಕೆಲವು ಸಮಸ್ಯೆಗಳಿವೆ ಆದರೆ ಆದಾಗ್ಯೂ ಬಂಧಿಸಲಾದ ಅವಳಿ-ಅಗಲದ ಊಹೆಯನ್ನು ಬಳಸಿಕೊಂಡು ವೇಗವನ್ನು ಹೆಚ್ಚಿಸಬಹುದು. ನಿಯತಾಂಕಗಳ ಕ್ರಮಾವಳಿಗಳು ಸಂಬಂಧಿತ ನಿಯತಾಂಕವನ್ನು ಹೊಂದಿರುವ ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿನ ಕ್ರಮಾವಳಿಯ ಸಮಸ್ಯೆಯನ್ನು ಸ್ಥಿರ-ನಿಯತಾಂಕ ಟ್ರ್ಯಾಕ್ಟಬಲ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಇದು ಶೃಂಗಗಳು ಮತ್ತು ನಿಯತಾಂಕ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿ, ಕೆಲವು ಸ್ಥಿರ ಮತ್ತು ಗಣಿಸಬಹುದಾದ ಕಾರ್ಯಕ್ಕಾಗಿ ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ಕ್ರಮಾವಳಿಯನ್ನು ಹೊಂದಿದ್ದರೆ. ಉದಾಹರಣೆಗೆ, ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವು ಈ ಅರ್ಥದಲ್ಲಿ ಸ್ಥಿರ-ನಿಯತಾಂಕವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ವಿಶ್ಲೇಷಣೆಯ ಶೈಲಿಯನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ತಿಳಿದಿರುವ ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಯನ್ನು ಹೊಂದಿರದ ಸಮಸ್ಯೆಗಳಿಗೆ ಅನ್ವಯಿಸಲಾಗುತ್ತದೆ, ಏಕೆಂದರೆ ಇಲ್ಲದಿದ್ದರೆ ಸ್ಥಿರ-ನಿಯತಾಂಕ ಟ್ರ್ಯಾಕ್ಟಬಿಲಿಟಿ ಕ್ಷುಲ್ಲಕವಾಗಿರುತ್ತದೆ. ಅಂತಹ ಅನೇಕ ಸಮಸ್ಯೆಗಳನ್ನು ಇನ್ಪುಟ್ನ ಭಾಗವಾಗಿ ಬೌಂಡೆಡ್ ಅಗಲದ ಸಂಕೋಚನ ಅನುಕ್ರಮವನ್ನು ನೀಡಿದಾಗ, ನಿಯತಾಂಕವಾಗಿ ಅವಳಿ-ಅಗಲದೊಂದಿಗೆ ಸ್ಥಿರ-ನಿಯತಾಂಕವನ್ನು ಪತ್ತೆಹಚ್ಚಬಹುದು ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಇದು ನಿರ್ದಿಷ್ಟವಾಗಿ, ಮೇಲೆ ಪಟ್ಟಿ ಮಾಡಲಾದ ಬೌಂಡೆಡ್ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ ಕುಟುಂಬಗಳಿಗೆ ಅನ್ವಯಿಸುತ್ತದೆ, ಇದಕ್ಕಾಗಿ ಸಂಕೋಚನ ಅನುಕ್ರಮವನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ನಿರ್ಮಿಸಬಹುದು. ಆದಾಗ್ಯೂ, ಗ್ರಾಫ್ನಲ್ಲಿ ಬೇರೆ ಯಾವುದೇ ರಚನೆ ತಿಳಿದಿಲ್ಲದಿದ್ದರೂ, ಕಡಿಮೆ ಅವಳಿ-ಅಗಲದ ಅನಿಯಂತ್ರಿತ ಗ್ರಾಫ್ಗೆ ಉತ್ತಮ ಸಂಕೋಚನ ಅನುಕ್ರಮವನ್ನು ಹೇಗೆ ಕಂಡುಹಿಡಿಯುವುದು ಎಂಬುದು ತಿಳಿದಿಲ್ಲ. ನೀಡಲಾದ ಸಂಕೋಚನ ಅನುಕ್ರಮಗಳೊಂದಿಗೆ ಬಂಧಿಸಲಾದ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ಗಳಿಗೆ ಸ್ಥಿರ-ನಿಯತಾಂಕದ ಟ್ರ್ಯಾಕ್ಟಬಲ್ ಸಮಸ್ಯೆಗಳೆಂದರೆಃ ನೀಡಲಾದ ಗ್ರಾಫ್ ಮಾದರಿಗಳು ಗ್ರಾಫ್ಗಳ ಮೊದಲ-ಕ್ರಮಾಂಕದ ತರ್ಕದಲ್ಲಿ ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ಗುಣಲಕ್ಷಣವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುವುದು. ಇಲ್ಲಿ, ಅವಳಿ-ಅಗಲ ಮತ್ತು ಆಸ್ತಿಯ ವಿವರಣೆಯ ಉದ್ದ ಎರಡೂ ವಿಶ್ಲೇಷಣೆಯ ನಿಯತಾಂಕಗಳಾಗಿವೆ. ಈ ರೀತಿಯ ಸಮಸ್ಯೆಗಳು ಸೀಮಿತ ಗಾತ್ರದ ಉಪಗ್ರಾಫ್ಗಳಿಗೆ ಉಪಗ್ರಾಫ್ ಐಸೊಮಾರ್ಫಿಸಮ್ ಅನ್ನು ಒಳಗೊಂಡಿವೆ, ಮತ್ತು ಕವರ್ಗಳಿಗೆ ಅಥವಾ ಸೀಮಿತ ಗಾತ್ರದ ಸೆಟ್ಗಳಲ್ಲಿ ಪ್ರಾಬಲ್ಯ ಸಾಧಿಸಲು ಶೃಂಗದ ಕವರ್ ಮತ್ತು ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿವೆ. ಗುಣಲಕ್ಷಣವನ್ನು ವಿವರಿಸುವ ತಾರ್ಕಿಕ ಸೂತ್ರದ ಉದ್ದದ ಮೇಲೆ ಈ ಸಾಮಾನ್ಯ ವಿಧಾನಗಳ ಅವಲಂಬನೆಯು ಟೆಟ್ರೆಶನಲ್ ಆಗಿದೆ, ಆದರೆ ಸ್ವತಂತ್ರ ಸೆಟ್, ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ ಮತ್ತು ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಗಳಿಗೆ ಇದನ್ನು ಸ್ವತಂತ್ರ ಅಥವಾ ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ನ ಗಾತ್ರದಲ್ಲಿ ಘಾತಾಂಕಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಬಹುದು, ಮತ್ತು ಸಬ್ಗ್ರಾಫ್ ಐಸೊಮಾರ್ಫಿಸಂಗೆ ಇದನ್ನು ಸಬ್ಗ್ರಾಫ್ನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ಫ್ಯಾಕ್ಟೋರಿಯಲ್ಗೆ ಕಡಿಮೆ ಮಾಡಬಹುದು. ಉದಾಹರಣೆಗೆ, ನಿರ್ದಿಷ್ಟ-ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿರುವ-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ಗೆ, ಸಂಕೋಚನ ಅನುಕ್ರಮದ ಮುಂದುವರಿದ ದಿಕ್ಕಿನಲ್ಲಿ ಕೆಂಪು ಗ್ರಾಫ್ಗಳ ಸಣ್ಣ ಸಂಪರ್ಕಿತ ಉಪಗ್ರಾಫ್ಗಳನ್ನು ಪರಿಗಣಿಸುವ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಮೂಲಕ-ವೆರ್ಟೆಕ್ಸ್ ಸ್ವತಂತ್ರ ಸೆಟ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಯ. ಘಾತೀಯ ಸಮಯದ ಊಹೆಯ ಅಡಿಯಲ್ಲಿ, ಘಾತಾಂಕದಲ್ಲಿನ ಲಾಗರಿಥಮಿಕ್ ಅಂಶಗಳವರೆಗೆ ಈ ಸಮಯದ ಮಿತಿಗಳು ಸೂಕ್ತವಾಗಿವೆ. ಗ್ರಾಫ್ಗಳ ಮೊದಲ-ಕ್ರಮಾಂಕದ ತರ್ಕವನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ಕ್ರಮಬದ್ಧವಾದ ಶೃಂಗಗಳೊಂದಿಗೆ ಗ್ರಾಫ್ಗಳಿಗೆ ವಿಸ್ತರಿಸಲು ಮತ್ತು ಈ ಕ್ರಮವನ್ನು ಪರೀಕ್ಷಿಸಬಹುದಾದ ತಾರ್ಕಿಕ ಮುನ್ಸೂಚನೆಗಳಿಗಾಗಿ, ಮಾದರಿ ಪರಿಶೀಲನೆಯು ಇನ್ನೂ ಬದ್ಧ ಅವಳಿ-ಅಗಲದ ಆನುವಂಶಿಕ ಗ್ರಾಫ್ ಕುಟುಂಬಗಳಿಗೆ ಸ್ಥಿರ-ನಿಯತಾಂಕವಾಗಿದೆ, ಆದರೆ ಮಿತಿಯಿಲ್ಲದ ಅವಳಿ-ಅಗಲದ ಆನುವಂಶಿಕ ಕುಟುಂಬಗಳಿಗೆ (ಪ್ರಮಾಣಿತ ಸಂಕೀರ್ಣತೆ-ಸೈದ್ಧಾಂತಿಕ ಊಹೆಗಳ ಅಡಿಯಲ್ಲಿ) ಅಲ್ಲ. ಅವುಗಳ ಅವಳಿ-ಅಗಲ ಮತ್ತು ಅವುಗಳ ಅತಿದೊಡ್ಡ ಗುಂಪಿನ ಗಾತ್ರದ ಕಾರ್ಯದಿಂದ ಸುತ್ತುವರಿದ ಹಲವಾರು ಬಣ್ಣಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಸುತ್ತುವರಿದ ಅವಳಿ-ಅಗಲದ ಬಣ್ಣದ ರೇಖಾಚಿತ್ರಗಳು. ಉದಾಹರಣೆಗೆ, ಅವಳಿ-ಅಗಲದ ತ್ರಿಕೋನ-ಮುಕ್ತ ಗ್ರಾಫ್ಗಳನ್ನು ದುರಾಸೆಯ ಬಣ್ಣದ ಅಲ್ಗಾರಿದಮ್ನಿಂದ ಬಣ್ಣ ಮಾಡಬಹುದು, ಅದು ಶೃಂಗಗಳನ್ನು ಅವು ಸಂಕುಚಿತಗೊಂಡ ಕ್ರಮದ ಹಿಂಭಾಗದಲ್ಲಿ ಬಣ್ಣ ಮಾಡುತ್ತದೆ. ಈ ಫಲಿತಾಂಶವು ಸುತ್ತುವರಿದ ಅವಳಿ-ಅಗಲದ ರೇಖಾಚಿತ್ರಗಳು χ-ಸುತ್ತುವರಿಯಲ್ಪಟ್ಟಿವೆ ಎಂಬುದನ್ನು ತೋರಿಸುತ್ತದೆ. ಸುತ್ತುವರಿದ ವಿರಳ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ ಕುಟುಂಬಗಳಿಗೆ, ಸಾಮಾನ್ಯ ಬಣ್ಣ ಸಂಖ್ಯೆಗಳು ಸುತ್ತುವರಿಯಲ್ಪಟ್ಟಿರುತ್ತವೆ. ಇಲ್ಲಿ, ಶೃಂಗಗಳನ್ನು ರೇಖೀಯವಾಗಿ ಕ್ರಮಗೊಳಿಸಬಹುದಾದರೆ, ಪ್ರತಿ ಶೃಂಗವು ಕ್ರಮದಲ್ಲಿ ಅತ್ಯಂತ ಮುಂಚಿನ ಶೃಂಗಗಳನ್ನು ತಲುಪಲು ಸಾಧ್ಯವಾದರೆ, ಕ್ರಮದಲ್ಲಿ ನಂತರದ ಶೃಂಗಗಳ ಮೂಲಕ ಉದ್ದದ ಮಾರ್ಗಗಳ ಮೂಲಕ ಸಾಮಾನ್ಯ ಬಣ್ಣದ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಶಾಸ್ತ್ರೀಯ ಕ್ರಮಾವಳಿಗಳ ವೇಗವರ್ಧನೆಗಳು ಸೀಮಿತವಾದ ಅವಳಿ-ಅಗಲದ ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿ, ರೇಖಾಚಿತ್ರವು ದಟ್ಟವಾಗಿದ್ದರೂ ಮತ್ತು ಈ ಸಮಯದ ಮಿತಿಗಿಂತ ಹೆಚ್ಚಿನ ಅಂಚುಗಳನ್ನು ಹೊಂದಿದ್ದರೂ ಸಹ, ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, ಅಗಲ-ಮೊದಲ ಹುಡುಕಾಟವನ್ನು ಮಾಡಲು ಸಾಧ್ಯವಿದೆ. ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳನ್ನು ಅವಳಿ-ಅಗಲವನ್ನೂ ಸಹ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಅನ್ವಯಿಸಲಾಗಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಬೌಂಡೆಡ್ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ಗಳಲ್ಲಿ, ಬೌಂಡೆಡ್ ಅಂದಾಜು ಅನುಪಾತದೊಂದಿಗೆ ಕನಿಷ್ಠ ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ಗೆ ಅಂದಾಜು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಿದೆ. ಇದು ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಗ್ರಾಫ್ಗಳಿಗೆ ವ್ಯತಿರಿಕ್ತವಾಗಿದೆ, ಇದಕ್ಕಾಗಿ ಲಾಗರಿದಮಿಕ್ಗಿಂತ ಉತ್ತಮವಾದ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಪಡೆಯುವುದು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ. ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಸೆಟ್ ಮತ್ತು ಗ್ರಾಫ್ ಬಣ್ಣದ ಸಮಸ್ಯೆಗಳನ್ನು ಬೌಂಡೆಡ್ ಅವಳಿ-ಅಗಲದ ಗ್ರಾಫ್ಗಳ ಬಹುಪದ ಸಮಯದಲ್ಲಿ, ಪ್ರತಿಯೊಂದಕ್ಕೂ ಅಂದಾಜು ಅನುಪಾತದೊಳಗೆ ಅಂದಾಜು ಮಾಡಬಹುದು. ಇದಕ್ಕೆ ವ್ಯತಿರಿಕ್ತವಾಗಿ, ಬಂಧಿಸಲಾದ ಅವಳಿ-ಅಗಲದ ಊಹೆಯಿಲ್ಲದೆ, ಈ ರೂಪದ ಯಾವುದೇ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಸಾಧಿಸುವುದು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ. ಉಲ್ಲೇಖಗಳು ಹೆಚ್ಚಿನ ಓದುವಿಕೆ ಗ್ರಾಫ್ ಇನ್ವೇರಿಯಂಟ್ಗಳು