The automated generation of humor remains a significant challenge in artificial intelligence, requiring not just language fluency but also creativity, contextual awareness, and the ability to handle subjective reasoning. While recent work has explored culturally-specific humor generation [Zhong et al., 2023], many systems still fall short. Standard "prompt and sample" techniques with Large Language Models (LLMs), for instance, often produce generic, templated, or repetitive jokes. Furthermore, LLM-based evaluations of humor can be inconsistent and fail to capture the multifaceted nature of comedy. To address these shortcomings, we introduce HumorPlanSearch, a comprehensive pipeline designed to systematically improve the quality, novelty, and contextual relevance of AI-generated humor. Our main contributions are as follows: We introduce a novel pipeline, HumorPlanSearch, that integrates strategic planning, a knowledge graph (KG), and iterative revision. We propose a multi-faceted evaluation metric, the Humor Generation Score (HGS), for more robust automated assessment. We demonstrate the effectiveness of culturally-aware Humor Chain-of-Thought (HuCoT) templates for generating nuanced humor. This holistic approach is designed to foster more sophisticated, adaptive, and genuinely amusing AI-generated content. 1